Bit Operations

The following will go over bit operations in C

ENABLE    0x01   // which is 00000001 in binary
DIRTY     0x02   // which is 00000010 in binary
MINE      0x04   // which is 00000100 in binary
BUSY      0x08   // which is 00001000 in binary

Notice that these are all in different locations in binary. As long as you are on the same type of machine (i.e. all IBM compatible PCs) then these values will be represented the same way in memory.

Assume you have a variable called flags. Initially it is 0, which means nothing. The flags variable can be used to hold the defined flags:

flags = flags | ENABLE;    // Now we are enabled
flags |= ENABLE;           // same as above

flags = flags | DIRTY;     // Now we are dirty.
flags |= DIRTY;            // same as above

The | (or) operation is used to "turn" on a flag.

To test if the flag is on, use the & (and) operator is used:

if (flags & ENABLE)
{
    // we are enabled
}

To toggle the flag (without knowing what it is), the ^ (xor) operator is used:

flags = flags ^ ENABLE;      // toggle the ENABLE bit
flags ^= ENABLE;             // same as above, but doing it a 
                             // second time changes it back to
                             // the original value

To turn off a flag, the & (and) operator and the ~ (complement) operator are used:

flags = flags & ~ENABLE;     // turn off ENABLE bit
flags &= ~ENABLE;            // same as above.

Note that if flags was written to a file, and then moved to an incompatible architecture, (from PC to Mac), then the values wouldn't necessarily be the same. Networks work properly because all host convert from the "local" format to the network format then back into the "local" format of the target.

& (and), | (or), ~ (complement), and ^ (xor) are used to bit-twiddle.

&, ~, and | are most commonly used for bit-wise flags, and also for I/O devices to change the values of a memory location w/o affecting all bits. They are also sometime used in pseudo-random number generators.

^ is used for simple cryptography and for various hashing functions.

b & (b - 1)       clears the trailing bit
b & -b            gives you the trailing bit

/*
**  Macros to manipulate bits in an array of char.
**  These macros assume CHAR_BIT is one of either 8, 16, or 32.
*/

#define MASK  CHAR_BIT-1
#define SHIFT ((CHAR_BIT==8)?3:(CHAR_BIT==16)?4:5)

#define BitOff(a,x)  ((void)((a)[(x)>>SHIFT] &= ~(1 << ((x)&MASK))))
#define BitOn(a,x)   ((void)((a)[(x)>>SHIFT] |=  (1 << ((x)&MASK))))
#define BitFlip(a,x) ((void)((a)[(x)>>SHIFT] ^=  (1 << ((x)&MASK))))
#define IsBit(a,x)   ((a)[(x)>>SHIFT]        &   (1 << ((x)&MASK)))

/* macros to extract the high and low bytes of 2-byte integers */
#define LoByte(x) ((x) & 0xff)
#define HiByte(x) ((x) >> 8)

Common terminology when dealing with bit operations

bit = 1 bit
crumb = 2 bits
nibble = 4 bits
byte = 8 bits
word = 16 bits
double word = 32 bits

Bit Counting Functions

/*
 * Counts the number of bits set. Is twice as fast as 
 * obvious shift and test method
 */
int bit_count(long x)
{
    int n = 0;

    if (x)
    {
        do 
        {
            n++;
        } while ((x &= x-1));
    }

    return(n);
}


/*
 * fast bit counter for 32 bit integers
 */
int bit_count32 (unsigned int w)
{
   w = (0x55555555 & w) + (0x55555555 & (w>> 1));
   w = (0x33333333 & w) + (0x33333333 & (w>> 2));
   w = (0x0f0f0f0f & w) + (0x0f0f0f0f & (w>> 4));
   w = (0x00ff00ff & w) + (0x00ff00ff & (w>> 8));
   w = (0x0000ffff & w) + (0x0000ffff & (w>>16));
   return w;
}


/*
 * even faster bit counter for 32 bit integers
 */
int bit_count32 (unsigned int w)
{
    const unsigned int all1   = ~0;
    const unsigned int mask1h = all1 /  3  << 1;
    const unsigned int mask2l = all1 /  5;
    const unsigned int mask4l = all1 / 17;
    w -= (mask1h & w) >> 1;
    w = (w & mask2l) + ((w>>2) & mask2l);
    w = w + (w >> 4) & mask4l;
    w += w >> 8;
    w += w >> 16;
    return w & 0xff;
}

Bit Functions

typedef enum {ERROR = -1, FALSE, TRUE} LOGICAL;

#define BitSet(arg,posn) ((arg) | (1L << (posn)))
#define BitClr(arg,posn) ((arg) & ~(1L << (posn)))
#define BitFlp(arg,posn) ((arg) ^ (1L << (posn)))
#define BitTst(arg,posn) (((arg) & (1L << (posn))) > 0)

#define BOOL(x) (!(!(x)))

Bit Operations AND / OR / XOR

bitwise AND (&)

0 AND 0 = 0    
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1 

0110 1011 1000 0101
0001 1111 1011 1001
---------------------
0000 1011 1000 0001

bitwise OR (|)

0 OR 0 = 0    
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1 

0110 1011 1000 0101
0001 1111 1011 1001
---------------------
0111 1111 1011 1101

bitwise XOR (^)

0 XOR 0 = 0    
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0    

0110 1011 1000 0101
0001 1111 1011 1001
---------------------
0111 0100 0011 1100