Efficient bit twiddling in C

Bit copy: To set or clear a bit within a byte variable based upon a bit in the same or other byte variable try:

(byte2 &= ~BITMASK2), (byte1 & BITMASK1) ? (byte2 |= BITMASK2) : 0;

Which could be encapsulated into a macro:

#define setmask(b1, m1, b2, m2) (((b2) &= ~(m2)), ((b1) & (m1)) ? ((b2) |= (m2)) : 0)

which you would use thusly:

        setmask(byte1, BITMASK1, byte2, BITMASK2);

The result for the PIC is:

        bcf     _byte2,3
        btfsc   _byte1,2
        bsf     _byte2,3

Which is very effecient. If you don't want to clear the bit first (e.g. if it was a port pin) then it would be:

(!(byte1 & BITMASK1) ? (byte2 &= ~BITMASK2) : 0), (byte1 & BITMASK1) ? (byte2 |= BITMASK2) : 0;

PIC - Bit operations@

Sign Extension: Extends the sign of a n value by invoking with SIGNEX(x, n-1)

#define SIGNEX(v, sb) ((v) | (((v) & (1 << (sb))) ? ~((1 << (sb))-1) : 0))

unsigned b; // number of bits representing the number in x
int x;      // sign extend this b-bit number to r
int r;      // resulting sign-extended number
int const m = 1U << (b - 1); // mask can be pre-computed if b is fixed

x = x & ((1U << b) - 1);  // (Skip this if bits in x above position b are already zero.)
r = (x ^ m) - m;

Count bits set: Counting bits set by lookup table

//table where value at addr is the number of bits set for that number
static const unsigned char BitsSetTable256[256] = {
#define B2(n) n,     n+1,     n+1,     n+2
#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
  B6(0), B6(1), B6(1), B6(2)
  };

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] + 
    BitsSetTable256[(v >> 8) & 0xff] + 
    BitsSetTable256[(v >> 16) & 0xff] + 
    BitsSetTable256[v >> 24]; 

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] + 
    BitsSetTable256[p[1]] + 
    BitsSetTable256[p[2]] +	
    BitsSetTable256[p[3]];


// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++) {
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
  }

PICList 2024 contributors: o List host: MIT, Site host massmind.org, Top posters @none found - Page Editors: James Newton, David Cary, and YOU! * Roman Black of Black Robotics donates from sales of Linistep stepper controller kits. * Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters. * Monthly Subscribers: Gregg Rew. on-going support is MOST appreciated! * Contributors: Richard Seriani, Sr.

  .