# Mark Needham

Thoughts on Software Development

## Bitwise operations in Ruby and Haskell

Part of one of the most recent problems in the Algorithms 2 course required us to find the ‘neighbours’ of binary values.

In this case a neighbour is described as being any other binary value which has an equivalent value or differs in 1 or 2 bits.

e.g. the neighbours of ‘10000’ would be ‘00000’, ‘00001’, ‘00010’, ‘00100’, ”01000′, ‘10001’, ‘10010’, ‘10011’, ‘10100’, ‘10101’, ‘10110’, ‘11000’, ‘11001’, ‘11010’ and ‘11100’

I initially treated ‘10000’ as an array of 1s and 0s and wrote a function to recursively come up with the above combinations before it was pointed out to me that it’d be much easier to use bit wise logic instead.

I don’t remember every having to write any code using bit wise operations since university so I thought I’d document what I learnt.

The first thing to do is convert those binary values into a decimal equivalent which is pretty easy in Ruby:

```> "10000".to_i(2) => 16```

In Haskell I stole a function from PLEAC to do the job:

```> import Data.Char > (foldr (\c s -> s * 2 + c) 0 . reverse . map digitToInt) "10000" 16```

I initially worked out the neighbours by hand but I need to work out how to convert that into code so I ran through an example.

We want to get from ‘10000’ (16) to ‘00000’ (0) which we can do by using an XOR operation:

Binary XOR Operator copies the bit if it is set in one operand but not both.

`'10000' XOR '10000'`

In Ruby it would read like this:

```> 16 ^ 16 => 0```

If we do the same XOR operation but changing the other bits instead we end up with all the neighbours of distance 1:

```> [0,1,2,4,16].map { |x| 16 ^ x } => [16, 17, 18, 20, 0]```

We can generalise the function that creates that array of values like so:

```> bits = 5 > offsets = (0..(bits - 1)).map { |x| 2 ** x } => [1, 2, 4, 8, 16]```

or if we want to use bit shifting:

```> offsets = (0..(bits - 1)).map { |x| 1 << x } => [1, 2, 4, 8, 16]```

With that approach we’re moving the “left operands value is moved left by the number of bits specified by the right operand.” i.e. we move ‘1’ left by 0 bits (from ‘1’to ‘1’), then by 1 bit (from ‘1’ to ’10’), then by 2 bits (from ‘1’ to ‘100’) and so on.

We still need to get all the neighbours which differ by 2 bits which we can do by getting all the ways that we can combine those offsets together. The combination function and Bitwise or do the trick here:

```> offsets.combination(2).to_a => [[1, 2], [1, 4], [1, 8], [1, 16], [2, 4], [2, 8], [2, 16], [4, 8], [4, 16], [8, 16]] > offsets.combination(2).to_a.map { |a,b| a|b } => [3, 5, 9, 17, 6, 10, 18, 12, 20, 24]```

Now if we put it all together:

```> initial_value = "10000" => "10000" > bits = initial_value.length => 5 > value = "10000".to_i(2) => 16 > single_bit_offsets = (0..(bits - 1)).map { |x| 1 << x } => [1, 2, 4, 8, 16] > all_the_offsets = offsets + offsets.combination(2).to_a.map { |a,b| a|b } => [1, 2, 4, 8, 16, 3, 5, 9, 17, 6, 10, 18, 12, 20, 24] > all_the_offsets.map { |offset| value ^ offset }.sort => [0, 1, 2, 4, 8, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28]```

The final Haskell version looks like this:

```> import Data.Char > import Data.Bits > import Data.List   > let initialValue = "10000" > let bits = length initialValue > let value = (foldr (\c s -> s * 2 + c) 0 . reverse . map digitToInt) initialValue > let singleBitOffsets = map (shiftL 1) [0..(bits - 1)] :: [Int] > let allTheOffsets = singleBitOffsets ++ map (\(x:y:_) -> (x .|. y)) (combinationsOf 2 singleBitOffsets) :: [Int] > Data.List.sort \$ map (xor value) allTheOffsets [0,1,2,4,8,17,18,19,20,21,22,24,25,26,28]```

I took the combinationsOf function from David Amos’ Combinatorics Generation library and it reads like so:

```-- subsets of size k combinationsOf 0 _ = [[]] combinationsOf _ [] = [] combinationsOf k (x:xs) = map (x:) (combinationsOf (k-1) xs) ++ combinationsOf k xs```

A real life version of this problem occurs in the world of genome analysis where scientists need to work out whether phylogenetic profiles are functionally linked.

Written by Mark Needham

December 31st, 2012 at 1:14 pm