// Simple and quite fast on many data sets // Slow on small numbers let clz n = let rec loop m c = match m with | 0 -> 32 | m when m < 0 -> c | _ -> loop (m <<< 1) (c + 1) loop n 0 // Faster method with less speed variation let clzImmutable n = let rec loop m c = match m with | 0 -> 32 | m when m < 0 -> c | m when (m &&& 0xFFFF0000) = 0 -> loop (m <<< 16) (c + 16) | m when (m &&& 0xFF000000) = 0 -> loop (m <<< 8) (c + 8) | m when (m &&& 0xF0000000) = 0 -> loop (m <<< 4) (c + 4) | m when (m &&& 0xC0000000) = 0 -> loop (m <<< 2) (c + 2) | _ -> loop (m <<< 1) (c + 1) loop n 0 // Perfect hashing using a de Bruijn sequence // About the same speed as clzImmutable // Look-up table is captured in the closure so that it is only evaluated once // Constant time, except on 0 let clzDeBruijn = let bruijn = [|31; 30; 3; 29; 2; 17; 7; 28; 1; 9; 11; 16; 6; 14; 27; 23; 0; 4; 18; 8; 10; 12; 15; 24; 5; 19; 13; 25; 20; 26; 21; 22|] function | 0 -> 32 | n -> let v = uint32 n let v = v ||| (v >>> 1) let v = v ||| (v >>> 2) let v = v ||| (v >>> 4) let v = v ||| (v >>> 8) let v = v ||| (v >>> 16) let v = (v >>> 1) + 1u bruijn.[int32 ((v * 0x077CB531u) >>> 27)] // Generally the fastest, except on 0 let clzMutable n = let mutable c = 0 let mutable m = n if (m &&& 0xFFFF0000) = 0 then m <- m <<< 16; c <- c + 16 if (m &&& 0xFF000000) = 0 then m <- m <<< 8; c <- c + 8 if (m &&& 0xF0000000) = 0 then m <- m <<< 4; c <- c + 4 if (m &&& 0xC0000000) = 0 then m <- m <<< 2; c <- c + 2 if (m &&& 0x80000000) = 0 then m <- m <<< 1; c <- c + 1 if m = 0 then c <- c + 1 c