In the course of working on ParsecClone I needed some code that could take in an arbitrary byte array and convert it to a corresponding bit array. The idea is if I have an array of
[|byte 0xFF;byte 0x01|]
Then I should get
I’ve done plenty of bit slingin’ in my day, and the trick is just to apply a sequence of bit masks to each byte and collect all the bit arrays. In other languages this is always a little bit of a pain, but in F# the solution was amazingly elegant
As with anything F#, I like to start with the data
type Bit = | One | Zero override this.ToString() = match this with | One -> "1" | Zero -> "0"
Make bit masks
Now lets generate the meat and potatoes of this: a sequence of bit masks
let bitMasks = Seq.unfold (fun bitIndex -> Some((byte(pown 2 bitIndex), bitIndex), bitIndex + 1)) 0 |> Seq.take 8 |> Seq.toList |> List.rev
fold takes a list and a seed and returns a single accumulated item, an
unfold takes a seed and generates a list. For those not familiar,
unfold takes a function of the signature
(State -> ('a * State) option) -> State -> Seq<'a>
Unfold takes a function with an argument that is the state, and returns an
item * state option tuple. The first element of the option is the element to be emitted in the sequence. The second item is the next state. If you return
None instead of
Some the infinite sequence will end. You can see that my state is the exponent n of 2^n which gives you the bit mask. The first iteration is 2^0, then 2^1, then 2^2, etc. By reversing it, I now have a bitmask that look like this:
[2^7; 2^6; 2^5; 2^4; 2^3; 2^2; 2^1; 2^0]
Byte to Bits
The next thing is to apply the bitmask to a byte.
let byteToBitArray b = List.map (fun (bitMask, bitPosition) -> if (b &&& bitMask) >>> bitPosition = byte(0) then Zero else One) bitMasks
The unusual thing here is that bitwise and is the
&&& operator and bitwise shift is the >>> operator. Not that weird, but different from other langauges.
Bytes to Bits
All that’s left is applying the byteToBitArray function to byte array to get a bit array
let bytesToBits (bytes:byte) = bytes |> Array.toList |> List.map byteToBitArray |> List.collect id |> List.toArray
And now to test it in fsi
> bytesToBits [|byte 0xFF;byte 0x01|];; val it : Bit  = [|One; One; One; One; One; One; One; One; Zero; Zero; Zero; Zero; Zero; Zero; Zero; One|]
Bits To UInt
We can even take a bit array and create a uint now too
let bitsToUInt (bits:Bit) = let positions = Array.zip bits (Array.rev [|0..Array.length bits - 1|]) Array.fold (fun acc (bit, index) -> match bit with | Zero -> acc | One -> acc + (pown 2 index)) 0 positions
First I zip the bit array with each position in the bit array. Then we just need to fold over the array and add the accumulator to 2^n if the bit is a one.
> [|One; One; One; One; One; One; One; Zero;|] |> bitsToUInt;; val it : int = 254
I really enjoyed working with the higher order functions that F# provides to make a simple and robust conversion. Working with strongly typed data felt more robust than dealing with just integers.