# Bit mask of lowest bit not set

Code
``` 01: unsigned int lowestBitNotSet(unsigned int x) 02: { 03:   return ~x & (x + 1); 04: } 05: 06: unsigned int lowestBitNotSetSimple(unsigned int x) 07: { 08:   // to be consistent with lowestBitNotSet 09:   if (x == ~0) 10:     return 0; 11: 12:   // shift right until finding a zero 13:   unsigned int result = 1; 14:   while ((x & result) != 0) 15:     result <<= 1; 16: 17:   return result; 18: } ``` bits.stephan-brumme.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 AND-mask 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

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: compiler: Visual C++ 2008 in: ecx ← x out: eax → result 01:   ; x + 1 02:   lea eax, DWORD PTR [ecx+1] 03:   ; ~x 04:   not ecx 05:   ; ~x & (x + 1) 06:   and eax, ecx lowestBitNotSetSimple: compiler: Visual C++ 2008 in: ecx ← x out: eax → result 01:   ; x == ~0 02:   cmp ecx, -1 03:   jne \$prepare 04:   xor eax, eax 05:   jmp \$finish 06:   \$prepare: 07:   ; int result = 1; 08:   mov eax, 1 09:   ; while ((x & result) != 0) 10:   test cl, al 11:   je \$finish 12:   \$loop: 13:   ; result <<= 1; 14:   add eax, eax 15:   test eax, ecx 16:   jne \$loop 17:   \$finish: ``` bits.stephan-brumme.com