Monday, 6 January 2014

Bit tricks in F#: integer logarithm

The following function computes the base-2 logarithm of the given integer:

let log2 v =
  let mutable v, r = v, 0
  if v &&& 0xFFFF0000 <> 0 then
    let s = 1 <<< 4
    v <- v >>> s
    r <- r ||| s
  if v &&& 0xFF00 <> 0 then
    let s = 1 <<< 3
    v <- v >>> s
    r <- r ||| s
  if v &&& 0xF0 <> 0 then
    let s = 1 <<< 2
    v <- v >>> s
    r <- r ||| s
  if v &&& 0xC <> 0 then
    let s = 1 <<< 1
    v <- v >>> s
    r <- r ||| s
  if v &&& 0x2 <> 0 then
    let s = 1 <<< 0
    r <- r ||| s
  r

No comments: