Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$ 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 &gt;&gt; 1; // first round down to one less than a power of 2 
v |= v &gt;&gt; 2;
v |= v &gt;&gt; 4;
v |= v &gt;&gt; 8;
v |= v &gt;&gt; 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) &gt;&gt; 27];
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 &lt;k$).