Wednesday, March 31, 2010

Bit Operations from TAoCP in F#

In the interest of keeping the blog active in the midst of tax time, dragging out the bit theme a bit longer, etc., here the bit enumerators based on Dr. Knuth's TAoCP (Fascicle 4.1) in F#. My earlier C# posts on this can be found here and here.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)

// Enumerate the bits in an integer.
let rec bits n = seq {
match n with
| 0 -> ()
| _ ->
let b = n&&&(-n)
yield b
yield! bits (n&&&(~~~b))

// Enumerate the power set of the bits in
// an integer, including the null set.
let powerSet =
let rec powerSet0 s n = seq {
yield s
match (s=n) with
| true -> ()
| _ -> yield! powerSet0 ((s-n)&&&n) n
powerSet0 0

// Test.
let x0 = Seq.toList (bits 0xDD)
let x1 = Seq.toList (powerSet 5)
let x2 = Seq.toList (powerSet 0xDD)
let x3 = Seq.toList (powerSet 7)

printf "Your breakpoint here."

No comments: