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

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
Performance Chart
CPU cycles
(full optimization,
lower values are better)

Assembler Output
lowestBitNotSet:
01:   ; x + 1
02:   lea eax, DWORD PTR [ecx+1]
03:   ; ~x
04:   not ecx
05:   ; ~x & (x + 1)
06:   and eax, ecx

lowestBitNotSetSimple:
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

Download The full source code including a test program is available for download.

References http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

More Twiddled Bits
  1. Absolute value of a float
  2. Absolute value of an integer
  3. Approximative inverse of a float
  4. Bit manipulation basics
  5. Bit mask of lowest bit not set
  6. Count bits set in parallel a.k.a. Population Count
  7. Detects zero bytes inside a 32 bit integer
  8. Endianess
  9. Extend bit width
  10. Float inverse square root approximation
  11. Float square root approximation
  12. Is power of two
  13. Minimum / maximum of integers
  14. Parity
  15. Position of lowest bit set
  16. Round up to the next power of two
  17. Sign comparison
  18. Sign of a 32 bit integer
  19. Swap two values
Extra: Javascript bit manipulator

... or go to the index