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.

Pingback: In the News: 2012-12-31 | Klaus' Korner()

Pingback: Geek Reading December 31, 2012 | Regular Geek()

Pingback: A new year’s idea: Share what you learn at Mark Needham()