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

[Dario Teixeira <darioteixeira@yahoo.com>]

Hi,

> Simpler and maybe faster:
> 
> let logbin (n: int32) =
>   let n = ref (Int32.add n 0l) and i = ref 0 in
>   if !n >= 0x10000l then (n := Int32.shift_right !n 16; i := 16);
>   if !n >= 0x100l then (n := Int32.shift_right !n 8; i := !i + 8);
>   if !n >= 0x10l then (n := Int32.shift_right !n 4; i := !i + 4);
>   if !n >= 0x4l then (n := Int32.shift_right !n 2; i := !i + 2);
>   if !n >= 0x2l then !i + 1 else !i

Thanks!  In my synthetic benchmark, this pure Ocaml solution comes very
close to the C-based "noalloc" one (the record holder so far), at least
on an x86_64.

Note that __builtin_ctz actually translates into a single opcode where
available (BSFL in x86_64), and I expect that a modern CPU will do a
decent job with it.  Therefore, despite that a C-based solution will
most likely prevent inlining (right?), it may be hard to beat...

Cheers,
Dario Teixeira