3 people like it.
Like the snippet!

Count leading zeros

Several ways of counting leading zeros in a binary number. Update: clzDeBruijn now captures the look-up table in the closure so that the table is only evaluated once and everything is contained in the main function.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54:

// 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

val clz : n:int -> int

Full name: Script.clz

val n : int

val loop : (int -> int -> int)

val m : int

val c : int

val clzImmutable : n:int -> int

Full name: Script.clzImmutable

val clzDeBruijn : (int -> int)

Full name: Script.clzDeBruijn

val bruijn : int []

val v : uint32

Multiple items
val uint32 : value:'T -> uint32 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.uint32

--------------------
type uint32 = System.UInt32

Full name: Microsoft.FSharp.Core.uint32

Multiple items
val int32 : value:'T -> int32 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int32

--------------------
type int32 = System.Int32

Full name: Microsoft.FSharp.Core.int32

val clzMutable : n:int -> int

Full name: Script.clzMutable

val mutable c : int

val mutable m : int

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/iq
Posted:	11 years ago
Author:	Bjørn Bæverfjord
Tags:	count leading zeros , find first set , bit twiddling hacks , clz