Counting 1-bits in a DWORD

Counting 1-bits in a DWORD (int32) using the 'divide and conquer' strategy

 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:

let countingBitsOn (dword : int32) : int32 =
  //Counting 1-bits using 'divide and conquer' strategy 
  //from Hacker's Delight, Henry S. Warren, Jr.
  let mutable x = dword
  x <- x - ((x >>> 1) &&& 0x55555555)
  x <- (x &&& 0x33333333) + ((x >>> 0x2) &&& 0x33333333); 
  x <- (x + (x >>> 0x4)) &&& 0x0F0F0F0F
  x <- x + (x >>> 0x8);
  x <- x + (x >>> 0x10);
  x &&& 0x0000003F

let countingBitsOff (dword : int32) : int32 = 32 - countingBitsOn dword

for x in [0xA; 0xFF; 0x100; 0x400; System.Int32.MinValue; System.Int32.MaxValue] do
    printfn "%11d #bits on = %2d #bits off = %2d" x (countingBitsOn x) (countingBitsOff x)

(*    

         10 #bits on =  2 #bits off = 30
        255 #bits on =  8 #bits off = 24
        256 #bits on =  1 #bits off = 31
       1024 #bits on =  1 #bits off = 31
-2147483648 #bits on =  1 #bits off = 31
 2147483647 #bits on = 31 #bits off =  1

*)

val countingBitsOn : dword:int32 -> int32

Full name: Script.countingBitsOn

val dword : int32

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 mutable x : int32

val countingBitsOff : dword:int32 -> int32

Full name: Script.countingBitsOff

val x : int

namespace System

type Int32 =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val MaxValue : int
    static val MinValue : int
    static member Parse : s:string -> int + 3 overloads
    static member TryParse : s:string * result:int -> bool + 1 overload
  end

Full name: System.Int32

field int.MinValue = -2147483648

field int.MaxValue = 2147483647

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

Raw view Test code New version

More information

Link:	http://fssnip.net/pX
Posted:	9 years ago
Author:	Fabio Galuppo
Tags:	bits , bit shifting , bit manipulation