Number of trailing zeroes

Posted: January 24, 2012 | Author: rslootma | Filed under: algorithms, Programming | Tags: bitset, De Bruijn, graph theory |3 Comments »

Last time, I hinted about using De Bruijn sequences for speeding up iteration of bit sets. It’s an old trick that (I think) was discovered by chess programmers in the 1960s (I really need a reference for this).
It’s a classic that yields elegant and quintessential code, but really needs a sidebar explanation of what’s going on.

The problem

For a binary number, write a function that determines the number of trailing zeroes, ie how many times you can divide this number by 2 without remainder.
The trivial implementation is this:

let rec ntz n =
    let rec loop acc n =
      if n land 1 = 1
      then acc
      else loop (acc+1) (n lsr 1)
    loop 0 n

It’s surprising to learn it’s possible to find the answer without looping at all.

Least significant one

If you look at the problem, you quickly realize there is only one 1 that matters. The least significant one.
It can be isolated like this:

lso = n land ((lnot n) + 1)

or (shorter)

lso = n land (-n)

Let’s look at a few examples for byte size numbers

n	bin(n)	bin (lnot n)	bin (-n)	lso
2	0000 0010	1111 1101	1111 1110	0000 0010
7	0000 0111	1111 1000	1111 1001	0000 0001
40	0010 1000	1101 0111	1101 1000	0000 1000
48	0011 0000	1100 1111	1101 0000	0001 0000

Now comes a bit of a detour into graph theory.

De Bruijn Graphs

A detailed introduction is found here, but the important thing to remember is how you construct this graph. The example below is a (2,3) graph. You start with a vertex 000. Then, starting at a vertex, you slide in (shift left and append) either a 1, or a 0, and draw an edge to the result node. Iterate and stop when you have them all.

So after the first step, you have this:

after the next step, you have:

and the closed graph is:

De Bruijn sequences

A De Bruijn sequence is just a shorthand for an Hamiltionian path (a path that visits every vertex once) through a De Bruijn graph. An example of an Hamiltonian path for the full graph above is:

000 -> 001 -> 010 -> 101 -> 011 -> 111 -> 110 -> 100 -> 000

A compact representation for this path can be recorded by writing down the start point and the choices made at every point. The example path yields following sequence:

00010111

When sliding through the sequence, one bit at a time with a window of 3 bits, each of the 8 possible 3 digit sequences appears exactly once.

n	index
000	0
001	1
010	2
011	4
100	7
101	3
110	6
111	5

The trick

The table above shows you at each node how many steps you’re from the source of the graph.
So if you multiply the sequence with the least significant one or our number, we can use the table to find out how many shifts we had.

for example: 00010111 * 0010000 = 00101110000. You keep the right most 8 bits 0111000.
By looking at the leftmost 3 (= 8-5) bits 011, which you find by shifting 5 positions to the right,
you see that they are at index 4 in the table. So the number has 4 trailing zeroes.

Summary

To find the number of trailing zeroes for an 8 bit number, you need

1. an 8-bit De Bruijn sequence: debruijn = 00010111
2. a table of 8 precomputed entries 0,1,2,4,7,3,6,5
3. the following formula:

   lso = n & (-n)
   ntz = table[(lso * debruijn) >> 5]
   

64 bit version

If you want to do this for 64 bits, you follow the exact same reasoning. You need a 64-bit debruijn sequence (there are 2^26 of them), and a precomputed table of size 64.

#define DEBRUIJN 0x22fdd63cc95386dULL
static uint32_t table [64] ;
void inittable (){
    uint64_t db = DEBRUIJN ;
    int i ;
    for (i=0 ; i < 64;++ i ) {
        table [db >> 58] = i ;
        db = db <<1;
    }
}

uint32_t ntz ( uint64_t n){
    n &= −n ;
    n ∗= DEBRUIJN ;
    n >>= 58;
    return table [n] ;
}

Use in bitsets

Suppose you’re representing a bitset as an array of 64 bit words. When iterating, you slide through the words, and if a bit is 1 you do your thing. If the rest of the word you’re sliding through only contains zeroes, you’re wasting effort. Knowing the number of trailing zeroes allows you to calculate the last index for the loop over the bits of a word.

A look at a random standard library

Java

There is a java.util.BitSet class that has been in the java standard library since 1.0. Since the source is open, we can inspect it. Let’s take a peek.
The iterator uses
Long.numberOfTrailingZeros(word)
and the implementation there is:

public static int numberOfTrailingZeros(long i) {
           // HD, Figure 5-14
           int x, y;
           if (i == 0) return 64;
           int n = 63;
           y = (int)i; if (y != 0) { n = n -32; x = y; } else x = (int)(i>>>32);
           y = x <<16; if (y != 0) { n = n -16; x = y; }
           y = x << 8; if (y != 0) { n = n - 8; x = y; }
           y = x << 4; if (y != 0) { n = n - 4; x = y; }
           y = x << 2; if (y != 0) { n = n - 2; x = y; }
           return n - ((x << 1) >>> 31);
}

(you can read the full source here: Long.java )

The “HD” reference in the source code points to Henry S. Warren, Jr.’s Hacker’s Delight, (Addison Wesley, 2002).

I will not comment on this.

Other languages

Left as an exercise for the reader

have fun,

Romain.

---