1 people like it.

Count set bits in a bigint and a BitArray

Count the number of bits in a bigint (System.Numerics.BigInteger) and a BitArray. Note that version 4 is the fastest.

 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: 
open System.Linq

let bitcount (b:bigint) =
    let mutable b = b
    let mutable count = 0
    while b <> bigint 0 do
        b <- b &&& (b-(bigint 1))
        count <- count + 1
    count

let bitcount2 (b:System.Collections.BitArray) = 
    (b:> System.Collections.IEnumerable).Cast<bool>()
    |> Seq.map (fun v -> if v then 1 else 0) 
    |> Seq.sum

let bitcount3 (b:System.Collections.BitArray) = 
    let mutable count = 0
    for bit in b do
        if bit then
            count <- count+1
    count

let bitcount4 (b:System.Collections.BitArray) = 
    let mutable count = 0
    for bit=0 to b.Length-1 do
        if b.Get(bit) then
            count <- count+1
    count
namespace System
namespace System.Linq
val bitcount : b:bigint -> int

Full name: Script.bitcount
val b : bigint
type bigint = System.Numerics.BigInteger

Full name: Microsoft.FSharp.Core.bigint
val mutable b : bigint
val mutable count : int
val bitcount2 : b:System.Collections.BitArray -> int

Full name: Script.bitcount2
val b : System.Collections.BitArray
namespace System.Collections
Multiple items
type BitArray =
  new : length:int -> BitArray + 5 overloads
  member And : value:BitArray -> BitArray
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit
  member Count : int
  member Get : index:int -> bool
  member GetEnumerator : unit -> IEnumerator
  member IsReadOnly : bool
  member IsSynchronized : bool
  member Item : int -> bool with get, set
  ...

Full name: System.Collections.BitArray

--------------------
System.Collections.BitArray(length: int) : unit
System.Collections.BitArray(bytes: byte []) : unit
System.Collections.BitArray(values: bool []) : unit
System.Collections.BitArray(values: int []) : unit
System.Collections.BitArray(bits: System.Collections.BitArray) : unit
System.Collections.BitArray(length: int, defaultValue: bool) : unit
type IEnumerable =
  member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable
type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val v : bool
val sum : source:seq<'T> -> 'T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sum
val bitcount3 : b:System.Collections.BitArray -> int

Full name: Script.bitcount3
val bit : bool
val bitcount4 : b:System.Collections.BitArray -> int

Full name: Script.bitcount4
val bit : int
property System.Collections.BitArray.Length: int
System.Collections.BitArray.Get(index: int) : bool

More information

Link:http://fssnip.net/jH
Posted:10 years ago
Author:Samuel Bosch
Tags: bigint , bits , bit manipulation , bitarray