Saturday, July 18, 2009

Bit manipulation tricks

These tricks let you operate on the bits of an unsigned integer individually. This can be useful for storing booleans in C when low memory usage is more important than speed.

To avoid problems with twos complement, let's assume that flags is declared with an unsigned type. On most systems unsigned int is 32 bits, and in such cases n should only hold values 0 to 31. n and test can be any integer type large enough to hold this range.

// Set the nth bit.
flags |= 1 << n;

// Clear the nth bit.
flags &= ~(1 << n);

// Flip/toggle the nth bit.
flags ^= 1 << x;

// Extract the xth bit as an integer and store it in test.
test = flags >> x & 1;

A quick note on the extraction; the following is more intuitive if you compare it the set, clear, and flip/toggle operations:

test = flags & (1 << n);

However these advantages come with some problems:

  1. test must be stored in an integer of a type the same size or larger than flags

  2. n must be stored in an integer of a type the same size or larger than flags, or cast to such a type before the bitshift.

  3. This method extracts 1 << n if the nth bit is set rather than 1. 99% of the time this is fine because you'll just be using the bit as a test in an if, while, or for statement, but that other 1% can be important, especially if you generalize these statements with a macro or a function.

No comments:

Post a Comment