
Bit mask of lowest bit not set 

Code 
01: unsigned int lowestBitNotSet(unsigned int x)
bits.stephanbrumme.com

Explanation 
On this website I mention an algorithm to detect the position of the lowest bit set (see lowestBitSet). Here I present an idea I saw on the internet (see references) to return a mask of the lowest bit NOT set. Of course, both can be easily concated to get the position of the lowest bit not set. The code works as follows: ~x turns all 0's into 1's (and vice versa). This gives us a nice ANDmask of all potential candidates. Now the second part of the formula is responsible for turning only the rightmost 0 into a 1. If the rightmost bit is 0, then x+1 turns this bit into 1 and leaves all other bits untouched. If there are a few 1's right of the rightmost 0, then x+1 flips all these 1's into 0's and overflows a 1 to the rightmost 0. 
Restrictions 
• if all bits are set, the algorithm returns 0 
These ads help me to pay my server bills 

Performance 
+ Intel® Pentium™ D: • lowestBitNotSet: ≈ 1.5 cycles per number • simple(1,2): ≈ 6 cycles per number • simple(mix): ≈ 13 cycles per number + Intel® Core™ 2: • lowestBitNotSet: ≈ 1.5 cycles per number • simple(1,2): ≈ 4 cycles per number • simple(mix): ≈ 10.5 cycles per number + Intel® Core™ i7: • lowestBitNotSet: ≈ 1.5 cycles per number • simple(1,2): ≈ 4 cycles per number • simple(mix): ≈ 10.5 cycles per number CPU cycles (full optimization, lower values are better) 
Assembler Output 
lowestBitNotSet:
bits.stephanbrumme.com

Download  The full source code including a test program is available for download. 
References 
http://www.catonmat.net/blog/lowlevelbithacksyouabsolutelymustknow/ 
More Twiddled Bits 
... or go to the index 