Number of trailing zeroes

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.

About these ads

3 Comments on “Number of trailing zeroes”

  1. Per Vognsen says:

    An Eulerian path visits every edge (not every vertex) once. You’re thinking of a Hamiltonian path. Your de Bruijn graph has an Eulerian path, but it visits 000 and 111 and all other vertices with total degree greater than 2 more than once. However, the line digraph of the de Bruijn graph (a sort of digraph dual that interchanges the roles of vertices and edges) also has a Eulerian path, and an Eulerian path in the line digraph clearly corresponds to a Hamiltonian path in the original graph.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.