11
$\begingroup$

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];
$\endgroup$
  • 2
    $\begingroup$ The idea comes from this paper supertech.csail.mit.edu/papers/debruijn.pdf. A de Brujn sequence of size $2^k$ is a way to represent all bit strings of size $k$ very concisely: each possible string appears exactly once as a contiguous subsequence. So if you shift the de Bruijn sequence by $n \leq 2^k$ bits and read off the last $k$ bits, you have a unique identifier for $n$. $\endgroup$ – Sasho Nikolov Oct 25 '13 at 2:03
  • 1
    $\begingroup$ By the way this only computes $\lceil \log_2 v \rceil$; and as written it only works for 32-bit integers. $\endgroup$ – Sasho Nikolov Oct 25 '13 at 2:10
  • 1
    $\begingroup$ @Sasho Turn into an answer? $\endgroup$ – Yuval Filmus Oct 25 '13 at 10:13
  • $\begingroup$ @SashoNikolov Thanks, added a ceiling function to the question $\endgroup$ – Yury Bayda Oct 26 '13 at 17:13
9
$\begingroup$

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$).

$\endgroup$
  • 3
    $\begingroup$ Note that you can use any de Bruijn sequence in this manner to compute $i$ given $2^i$. However, you cannot use an arbitrary de Bruijn sequence to compute $i$ given $2^i - 1$. Here 0x07C4ACDD = 00000111110001001010110011011101 seems to be a de Bruijn sequence with some additional properties, thanks to which the additional $-1$ does not ruin this approach. $\endgroup$ – Jukka Suomela Oct 27 '13 at 16:55
  • $\begingroup$ Thanks @JukkaSuomela, I was a bit confused about that. I guess you can always just add 1 to $v$ though. $\endgroup$ – Sasho Nikolov Oct 27 '13 at 17:23
5
$\begingroup$

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...'

$\endgroup$
  • 1
    $\begingroup$ This is the only answer that deals with why multiplication of De Bruijn by 2^n-1 works, as opposed to 2^n, which is just a shift. I would love it if someone could expand on the "intuition" of #3 above. How did Eric Cole come up with this? Trial and error? Or some understanding of what actually happens to the bits when you multiply by 2^n-1? $\endgroup$ – FarmerBob Oct 20 '14 at 7:10
1
$\begingroup$
  • 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); //clr 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.enter image description here. 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.

$\endgroup$
  • $\begingroup$ Finally found: B(2,6) 0x3f08a4c6acb9dbd -- a 64bit de bruijn sequence with the 'dickinson property'. I have found at least 122K such a sequences. $\endgroup$ – FrantzelasG Apr 20 '17 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.