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

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

<pre><code>11111011100110101100010100100000
</code></pre></li>
<li><p>Type Y: bits [27,31] of $2^i \cdot c$ are distinct for $i = 0, 1, ..., 31$. This is what <a href="http://supertech.csail.mit.edu/papers/debruijn.pdf" rel="noreferrer">Leiserson et al.</a> uses. Examples:</p>

<pre><code>00000100011001010011101011011111
00001111101110011010110001010010
</code></pre></li>
<li><p>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:</p>

<pre><code>00000111110001001010110011011101  (07C4ACDD)
10000111110001001010110011011101
01111000001110110101001100100011
11111000001110110101001100100011
</code></pre></li>
</ul>

<p>Some observations based on quick experiments (I hope I got these right):</p>

<ol>
<li><p>There are 65536 integers of type X.</p></li>
<li><p>There are 4096 integers of type X + Y. These are precisely those integers of type X that begin with sequence '0000...'</p>

<ul>
<li>intuition: with leading zeroes, rotation = shifting?</li>
</ul></li>
<li><p>There are 256 integers of type X + Y + Z. These are precisely those integers of type X that begin with sequence '0000011111...'</p>

<ul>
<li>intuition: ??</li>
</ul></li>
<li><p>All integers of type Y are also of type X.</p></li>
<li><p>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...'</p></li>
</ol>

CC BY-SA 3.0
2014-10-20T07:10:52.437Z
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?
FarmerBob
CC BY-SA 3.0
2013-10-27T23:19:12.717Z
2013-10-27T23:19:12.717Z
Jukka Suomela
<ul>
<li>Where does this constant comes from?</li>
</ul>
<blockquote>
<p>Quoting: &quot;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&quot;.
[graphics.stanford.edu/~seander/bithacks.html]</p>
</blockquote>
<p>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:<pre>    v ^= (v &gt;&gt; 1);  // clear all bits except MSB set after the cascading or-shift.</pre></p>
<ul>
<li>Results (bruteforce)</li>
</ul>
<blockquote>
<p>Seq.Type | No. Integers | No. D.B.Seq. with | without Rotations | with Dickinson Property<br />
B(2, 3) | 256 |  16 | 2 | 1<br />
B(2, 4) | 64Ki | 256 | 16 | 4<br />
B(2, 5) | 04Gi | 64Ki | 02Ki | 256<br />
B(2, 6) | 16Ei | 04Gi | 64Mi | ??</p>
</blockquote>
<ul>
<li>The special property</li>
</ul>
<blockquote>
<p>The operation (<span class="math-container">${0x7C4ACDD}$</span> <span class="math-container">$*$</span> (<span class="math-container">$2^k$</span>-<span class="math-container">${1}$</span>))<span class="math-container">$\pmod {2^{32}}$</span>, <span class="math-container">$32\ge k\ge1$</span> 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 <a href="http://en.wikipedia.org/wiki/Linear-feedback_shift_register" rel="nofollow noreferrer">LFSR</a> 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) &gt;&gt; 27 would fail. Also note only the 5 MSBits form this LFSR, eg. the 5 LSBits sum is 166 rather 496.<a href="https://i.sstatic.net/6SUVa.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6SUVa.png" alt="enter image description here" /></a>. The pattern below diagonal line is an artifact of multiplication by (<span class="math-container">$2^k$</span>-<span class="math-container">${1}$</span>)</p>
</blockquote>
<ul>
<li>Lexicographically smallest binary de Bruijn sequences with Dickinson Property</li>
</ul>
<blockquote>
<p>[B(2,3): 0x1D][B(2,4): 0x0F2D][B(2,5): 0x7C4ACDD][B(2,6): Still Searching]</p>
</blockquote>
<p>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>
<blockquote>
<p>P.S. I did not cover the LUT construction, which is easily deduced if you understand the working principles of algorithms.</p>
</blockquote>

CC BY-SA 3.0
2017-04-20T23:53:22.487Z
Finally found: B(2,6) 0x3f08a4c6acb9dbd -- a 64bit de bruijn sequence with the 'dickinson property'. I have found at least 122K such a sequences.
FranG
CC BY-SA 4.0
2020-10-04T12:08:59.547Z
Thanks for `0x3f08a4c6acb9dbd`. It also seems to help with another issue I've battled for a long time. I often have to produce an single 32-bit hash of **two adjacent** 32-bit integers--in the case where each is expected to have extremely low entropy. Think maybe the lowest 0 to perhaps about 9 LSBs only, per each. So there's 0 to 18 bits of combined entropy you want to maximally preserve and distribute, always across exactly 32. But you don't know exactly how it's distributed, and even if you did, the two clumps are separated by about 20 zeros. Unprincipled salt values are a fool's errand...
Glenn Slayden
CC BY-SA 4.0
2020-10-04T12:10:26.770Z
...seeming to always end up revealing gaps and patterns for specific--but entirely common--input scenarios ("whack-a-mole" style). But with your magic number, just rudely coercing a single 64-bit multiply on the 32/32 tuple and then taking the **hi** 32-bits for the result seems to finally subdue the challenge of balancing such coarse input variation, *i.e*, with noticeably improved consistency. I haven't actually measured the retained entropy yet, but perhaps this math could be somehow acting to maximize...?
Glenn Slayden
CC BY-SA 4.0
2017-03-10T04:19:02.767Z
2020-12-12T21:07:30.427Z
2020-12-12T21:07:30.427Z
FranG
<p>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.</p>

<p>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$. </p>

<p>The interesting part is the de Bruijn trick, which comes from this paper of <a href="http://supertech.csail.mit.edu/papers/debruijn.pdf">Leiserson, Prokop and Randall</a> (apparently MIT professors spend time doing bit hacks :) ). What you need to know about <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence">de Bruijn sequences</a> 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$). </p>

CC BY-SA 3.0
2013-10-27T16:55:42.833Z
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.
Jukka Suomela
CC BY-SA 3.0
2013-10-27T17:23:03.440Z
Thanks @JukkaSuomela, I was a bit confused about that. I guess you can always just add 1 to $v$ though.
Sasho Nikolov
CC BY-SA 3.0
2013-10-25T20:00:18.763Z
2013-10-25T20:11:15.280Z
2013-10-25T20:11:15.280Z
Sasho Nikolov
<p>Sean Anderson published <a href="http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn" rel="noreferrer">bit twiddling hacks</a> 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.</p>

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

<pre><code>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];
</code></pre>

CC BY-SA 3.0
2013-10-25T02:03:42.297Z
The idea comes from this paper http://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$.
Sasho Nikolov
CC BY-SA 3.0
2013-10-25T02:10:38.313Z
By the way this only computes $\lceil \log_2 v \rceil$; and as written it only works  for 32-bit integers.
Sasho Nikolov
CC BY-SA 3.0
2013-10-25T10:13:00.313Z
@Sasho Turn into an answer?
Yuval Filmus
CC BY-SA 3.0
2013-10-26T17:13:18.927Z
@SashoNikolov Thanks, added a ceiling function to the question
Yury Bayda
<nt.number-theory><comp-number-theory>
Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$
Yury Bayda
# Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$

(Asked by: username_0 on 2013-10-24)

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];

**Tags:** nt.number-theory, comp-number-theory
> **Comments:**
> **username_1**: The idea comes from this paper http://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$.  
> **username_1**: By the way this only computes $\lceil \log_2 v \rceil$; and as written it only works  for 32-bit integers.  
> **username_2**: @Sasho Turn into an answer?  
> **username_0**: @SashoNikolov Thanks, added a ceiling function to the question  

---

## 3 answers

### Answer by username_1 on 2013-10-25. Score: 10 | Accepted answer

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](http://supertech.csail.mit.edu/papers/debruijn.pdf) (apparently MIT professors spend time doing bit hacks :) ). What you need to know about [de Bruijn sequences](http://en.wikipedia.org/wiki/De_Bruijn_sequence) 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

> **Comments:**
> **username_3**: 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.  
> **username_1**: Thanks @JukkaSuomela, I was a bit confused about that. I guess you can always just add 1 to $v$ though.  

---

### Answer by username_3 on 2013-10-27. Score: 7

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

There are 65536 integers of type X.
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?

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

intuition: ??

All integers of type Y are also of type X.
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...'

> **Comments:**
> **username_4**: 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?  

---

### Answer by username_5 on 2017-03-10. Score: 2

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.

> **Comments:**
> **username_5**: Finally found: B(2,6) 0x3f08a4c6acb9dbd -- a 64bit de bruijn sequence with the 'dickinson property'. I have found at least 122K such a sequences.  
> **username_6**: Thanks for `0x3f08a4c6acb9dbd`. It also seems to help with another issue I've battled for a long time. I often have to produce an single 32-bit hash of **two adjacent** 32-bit integers--in the case where each is expected to have extremely low entropy. Think maybe the lowest 0 to perhaps about 9 LSBs only, per each. So there's 0 to 18 bits of combined entropy you want to maximally preserve and distribute, always across exactly 32. But you don't know exactly how it's distributed, and even if you did, the two clumps are separated by about 20 zeros. Unprincipled salt values are a fool's errand...  
> **username_6**: ...seeming to always end up revealing gaps and patterns for specific--but entirely common--input scenarios ("whack-a-mole" style). But with your magic number, just rudely coercing a single 64-bit multiply on the 32/32 tuple and then taking the **hi** 32-bits for the result seems to finally subdue the challenge of balancing such coarse input variation, *i.e*, with noticeably improved consistency. I haven't actually measured the retained entropy yet, but perhaps this math could be somehow acting to maximize...?  

---

