Bitwise operations in OCaml

Question

What is the most idiomatic way to write bit-twiddling code in OCaml? I know about the very cool Bitstring library, but while this would be a great way to parse binary data in some protocol, it doesn't support bitwise operations like xor or shifting.

I believe that the underlying data structure used by that library is just OCaml strings, which I know are mutable (and relatively compact? I think I read that there is little overhead somewhere...) byte arrays, but you can't conveniently do many bitwise operations on strings as byte arrays since xor, shifts and so on are not defined on chars, but only on the integer types, so you have to cast back and forth between ints and chars... for instance, logical shift left defined on chars (bytes):

let byte_lsl (x : char) (n : int) : char =
    Char.chr (255 land (Char.code x lsl n))

# byte_lsl '\x0f' 1 ;;
- : char = '\030'

Is this the best we can do?

Presumably if the compiler isn't packing chars into machine words already, this isn't actually inefficient and is about the same as the situation in Java... but Haskell and Standard ML both provide smaller unsigned integer types which results in much clearer code, IMHO.

http://www.standardml.org/Basis/word.html#Word8:STR:SPEC

http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Word.html#t:Word8

Answer 1

If you have lots of bits that you want to pack efficiently, you could consider using the Bigarraylibrary.

I also think it would be fine to use strings. The extra functions Char.code and Char.chr don't actually generate any code. They just cause data to be reinterpreted with a new type. The only problem (that I can think of) with strings is that there is a fairly small limit on string size in the 32-bit model. I have hit this limit myself a few times.