Re: [Caml-list] Re: Binary logarithm of a power of 2

[Matteo Frigo <athena@fftw.org>]

A way exists to compute the binary logarithm with one multiplication and
a couple of shifts.  See Charles E. Leiserson, Harald Prokop, and Keith
H. Randall: Using de Bruijn Sequences to Index a 1 in a Computer Word.

The idea is that a magic 64-bit string of zeros and ones exists such
that all possible strings of 6 bits appear as substrings of the string.
Such a sequence is called a "de Bruijn Sequence".  Let K be such a
string interpreted as an int64.  Then K * 2^n shifts K to the left by n
places, leaving a unique encoding of n in the upper 6 bits of the
product.

Knuth Vol. 4A remarks that this is an old trick, invented but not
published by some gentleman at IBM in the late sixties.  (Sorry, I don't
have Knuth at hand for an exact reference.)  However the 1998 paper by
Leiserson et al. should be available via google.

Regards,
Matteo Frigo