Bit twiddling: which bit is set?

by

Finally an optimal solution. See the end of this section for what to do when the input is guaranteed to have exactly one non-zero bit: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

Here’s the code:

static const int MultiplyDeBruijnBitPosition2[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];

You may be able to adapt this to a direct multiplication-based algorithm for 64-bit inputs; otherwise, simply add one conditional to see if the bit is in the upper 32 positions or the lower 32 positions, then use the 32-bit algorithm here.

Update: Here’s at least one 64-bit version I just developed myself, but it uses division (actually modulo).

r = Table[v%67];

For each power of 2, v%67 has a distinct value, so just put your odd primes (or bit indices if you don’t want the odd-prime thing) at the right positions in the table. 3 positions (0, 17, and 34) are not used, which might be convenient if you also want to accept all-bits-zero as an input.

Update 2: 64-bit version.

r = Table[(uint64_t)(val * 0x022fdd63cc95386dull) >> 58];

This is my original work, but I got the B(2,6) De Bruijn sequence from this chess site so I can’t take credit for anything but figuring out what a De Bruijn sequence is and using Google. 😉

Some additional remarks on how this works:

The magic number is a B(2,6) De Bruijn sequence. It has the property that, if you look at a 6-consecutive-bit window, you can obtain any six-bit value in that window by rotating the number appropriately, and that each possible six-bit value is obtained by exactly one rotation.

We fix the window in question to be the top 6 bit positions, and choose a De Bruijn sequence with 0’s in the top 6 bits. This makes it so we never have to deal with bit rotations, only shifts, since 0’s will come into the bottom bits naturally (and we could never end up looking at more than 5 bits from the bottom in the top-6-bits window).

Now, the input value of this function is a power of 2. So multiplying the De Bruijn sequence by the input value performs a bitshift by log2(value) bits. We now have in the upper 6 bits a number which uniquely determines how many bits we shifted by, and can use that as an index into a table to get the actual length of the shift.

This same approach can be used for arbitrarily-large or arbitrarily-small integers, as long as you’re willing to implement the multiplication. You simply have to find a B(2,k) De Bruijn sequence where k is the number of bits. The chess wiki link I provided above has De Bruijn sequences for values of k ranging from 1 to 6, and some quick Googling shows there are a few papers on optimal algorithms for generating them in the general case.

More Related Contents:

  1. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  2. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  3. Arithmetic bit-shift on a signed integer
  4. Are the shift operators () arithmetic or logical in C?
  5. What is Bit Masking?
  6. Rounding up to next power of 2
  7. Catch and compute overflow during multiplication of two large integers
  8. Find most significant bit (left-most) that is set in a bit array
  9. Fast computing of log2 for 64-bit integers
  10. Extracting bits with a single multiplication
  11. Bitwise operators and “endianness”
  12. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  13. Bitfield manipulation in C
  14. Fastest way to clamp a real (fixed/floating point) value?
  15. What’s bad about shifting a 32-bit variable 32 bits?
  16. warning: left shift count >= width of type
  17. set the m-bit to n-bit [closed]
  18. Bitshift and integer promotion?
  19. Encoding int value as an IEEE-754 float (binary32)
  20. C reverse bits in unsigned integer
  21. How to define and work with an array of bits in C?
  22. Implementing Logical Right Shift in C
  23. How do I get bit-by-bit data from an integer value in C?
  24. Algorithm to generate bit mask
  25. How does this bitwise operation check for a power of 2?
  26. Check if a number is non zero using bitwise operators in C
  27. Decimal to Binary
  28. C Programming – XOR Bitwise Operation
  29. Order of fields when using a bit field in C
  30. What is bit masking?

Leave a Comment