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

[Johannes <adhocrocker@gmail.com>]

A link to the de Bruijn paper can be found on the "Bit Twiddling Hacks" page
linked earlyier in this thread:
http://graphics.stanford.edu/~seander/bithacks.html

I used it myself -- although with JavaScript and did not run any benchmarks --
and I liked the approach, very neat.

2011/5/28 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
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>