Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$

Question

Sean Anderson published bit twiddling hacks containing the Eric Cole's algorithm to find the $\lceil\log_2 v \rceil$ of an $N$-bit integer $v$ in $O(\lg(N))$ operations with multiply and lookup.

The algorithm relies on a "magic" number from De Bruijn sequence. Can anybody explain fundamental math properties of the sequence used here?

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

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

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

Answer 1

First note that this algorithm only computes $\lceil \log_2 v \rceil$, and as the code is written, it works only for $v$ that fit in a $32$-bit word.

The sequence of shifts and or-s that appears first has the function of propagating the leading 1-bit of $v$ all the way down to the least significant bit. Numerically, this gives you $2^{\lceil \log_2 v \rceil} - 1$.

The interesting part is the de Bruijn trick, which comes from this paper of Leiserson, Prokop and Randall (apparently MIT professors spend time doing bit hacks :) ). What you need to know about de Bruijn sequences is that they represent all possible sequences of a given length in a way that's as compressed as possible. Precisely, a de Brujn sequence over the alphabet $\{0, 1\}$ is a binary string $s$ of length $2^k$ such that each length $k$ binary string appears exactly once as a contiguous substring (wrap around is allowed). The reason this is useful is that if you have a number $X$ whose bit representation is a de Bruijn sequence (padded with $k$ zeros), then the top $k$ bits of $2^iX$ uniquely identify $i$ (as long as $i <k$).

Answer 2

Some comments (not really an answer). Let's classify 32-bit integers $c$ as follows:

• Type X: $c$ (as a binary string) is De Bruijn sequence (for all rotations, bits [27,31] are distinct). An example:

  11111011100110101100010100100000
  

• Type Y: bits [27,31] of $2^i \cdot c$ are distinct for $i = 0, 1, ..., 31$. This is what Leiserson et al. uses. Examples:

  00000100011001010011101011011111
  00001111101110011010110001010010
  

• Type Z: bits [27,31] of $(2^{i+1} - 1) \cdot c$ are distinct for $i = 0, 1, ..., 31$. This is what we need in the original question. Examples:

  00000111110001001010110011011101  (07C4ACDD)
  10000111110001001010110011011101
  01111000001110110101001100100011
  11111000001110110101001100100011
  

Some observations based on quick experiments (I hope I got these right):

1. There are 65536 integers of type X.

2. There are 4096 integers of type X + Y. These are precisely those integers of type X that begin with sequence '0000...'

   • intuition: with leading zeroes, rotation = shifting?

3. There are 256 integers of type X + Y + Z. These are precisely those integers of type X that begin with sequence '0000011111...'

   • intuition: ??

4. All integers of type Y are also of type X.

5. However, there are also 768 integers of type Z that are neither of type X nor of type Y. These begin with '1000011111...', '0111100000...', or '1111100000...'

Answer 3

• Where does this constant comes from?

Quoting: "On December 10, 2009, Mark Dickinson shaved off a couple operations by requiring v be rounded up to one less than the next power of 2 rather than the power of 2". [graphics.stanford.edu/~seander/bithacks.html]

This particullar constant is a De Bruijn Sequence with Binary alphabet but with an extra property. I'm gonna call it the 'Marc Dickinson Property' since the original algorithm could be implemented without these special D.B. sequences. By appending 2 extra operations we could use any ordinary D.B. sequence. Operation:

    v ^= (v >> 1);  // clear all bits except MSB set after the cascading or-shift.

• Results (bruteforce)

Seq.Type | No. Integers | No. D.B.Seq. with | without Rotations | with Dickinson Property
B(2, 3) | 256 | 16 | 2 | 1
B(2, 4) | 64Ki | 256 | 16 | 4
B(2, 5) | 04Gi | 64Ki | 02Ki | 256
B(2, 6) | 16Ei | 04Gi | 64Mi | ??

• The special property

The operation (${0x7C4ACDD}$ $*$ ($2^k$-${1}$))$\pmod {2^{32}}$, $32\ge k\ge1$ produces 32 results on which if we discard all but the 5 MSB bits and then stack them, the 5 bit wide column forms a LFSR which indexes all 32 permutations of a 5bit string 0 - 31. Other De Bruijn B(2,5) constants might index 31 out of 32 permutations of 5bit string but the operation (v * 0x07C4ACDD) >> 27 would fail. Also note only the 5 MSBits form this LFSR, eg. the 5 LSBits sum is 166 rather 496.. The pattern below diagonal line is an artifact of multiplication by ($2^k$-${1}$)

• Lexicographically smallest binary de Bruijn sequences with Dickinson Property

[B(2,3): 0x1D][B(2,4): 0x0F2D][B(2,5): 0x7C4ACDD][B(2,6): Still Searching]

If you were hoping for an elegant mathematical formula to describe them or theorem to produce them or something similar, i think this would require profound insight into number theory and possibly other fields which is beyond my skillset. If i where to make a wild guess i whould bet they could be produced by cellural automata. This is not an answer why? on a rigorous base but an attempt to intuitively understand why it works and why it works properly, so you can use it with confidence.

P.S. I did not cover the LUT construction, which is easily deduced if you understand the working principles of algorithms.