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

[Norman Hardy <norm@cap-lore.com>]

On 2011 May 27, at 22:29 , Gabriel Kerneis wrote:

> On Fri, May 27, 2011 at 10:21:09AM -0700, Dario Teixeira wrote:
>> Incidentally, I found a web page with lots of cool bit-twiddling hacks,
>> which includes several solutions to the binary logarithm problem:
>> http://graphics.stanford.edu/~seander/bithacks.html
> 
> Some more of them:
> http://www.cl.cam.ac.uk/~am21/hakmemc.html
> 
> Those are the (famous) HAKMEM tricks, translated to C by Alan Mycroft.
> Probably of no practical use, but learning what the fixed point of the float
> function was on a PDP-10 is priceless...
> 
> Best,
> -- 
> Gabriel
> 
> -- 
> 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
> 

In the spirit of HAKMEM here is a routine, in C, that counts the low zero bits of an integer less than 2^31:
http://cap-lore.com/code/fb/
In machine language it might require just 7 instructions with no branches.
I think that it cannot be improved to handle input greater than 2^31.
A 63 bit version should be possible.