Editing De Bruijn sequence (section)

===Finding least- or most-significant set bit in a word===
A de Bruijn sequence can be used to quickly find the index of the least significant set bit ("right-most 1") or the most significant set bit ("left-most 1") in a [[Word (data type)|word]] using [[bitwise operation]]s and multiplication.<ref>{{harvtxt|Anderson|1997–2009}}; {{harvtxt|Busch|2009}}</ref> The following example uses a de Bruijn sequence to determine the index of the least significant set bit (equivalent to counting the number of trailing '0' bits) in a 32 bit unsigned integer:

<syntaxhighlight lang="cpp">
uint8_t lowestBitIndex(uint32_t v)
{       
  static const uint8_t BitPositionLookup[32] = // hash table
  {
    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
  };
  return BitPositionLookup[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
}
</syntaxhighlight>

The <code>lowestBitIndex()</code> function returns the index of the least-significant set bit in ''v'', or zero if ''v'' has no set bits. The constant 0x077CB531U in the expression is the ''B''&thinsp;(2,&nbsp;5) sequence 0000&thinsp;0111&thinsp;0111&thinsp;1100&thinsp;1011&thinsp;0101&thinsp;0011&thinsp;0001 (spaces added for clarity). The operation <code>(v & -v)</code> zeros all bits except the least-significant bit set, resulting in a new value which is a power of 2. This power of 2 is multiplied (arithmetic modulo 2<sup>32</sup>) by the de Bruijn sequence, thus producing a 32-bit product in which the bit sequence of the 5 MSBs is unique for each power of 2. The 5 MSBs are shifted into the LSB positions to produce a hash code in the range [0, 31], which is then used as an index into [[hash table]] BitPositionLookup. The selected hash table value is the bit index of the least significant set bit in ''v''.

The following example determines the index of the most significant bit set in a 32 bit unsigned integer:

<syntaxhighlight lang="cpp">
uint32_t keepHighestBit(uint32_t n)
{
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

uint8_t highestBitIndex(uint32_t v)
{
    static const uint8_t BitPositionLookup[32] = { // hash table
         0,  1, 16,  2, 29, 17,  3, 22, 30, 20, 18, 11, 13,  4,  7, 23,
        31, 15, 28, 21, 19, 10, 12,  6, 14, 27,  9,  5, 26,  8, 25, 24,
    };
    return BitPositionLookup[(keepHighestBit(v) * 0x06EB14F9U) >> 27];
}
</syntaxhighlight>

In the above example an alternative de Bruijn sequence (0x06EB14F9U) is used, with corresponding reordering of array values. The choice of this particular de Bruijn sequence is arbitrary, but the hash table values must be ordered to match the chosen de Bruijn sequence. The <code>keepHighestBit()</code> function zeros all bits except the most-significant set bit, resulting in a value which is a power of 2, which is then processed as in the previous example.