Mark Needham

Thoughts on Software Development

Bitwise operations in Ruby and Haskell

with 4 comments

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.

Be Sociable, Share!

Written by Mark Needham

December 31st, 2012 at 1:14 pm

Posted in Haskell,Ruby

Tagged with , ,

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

  • Pingback: Geek Reading December 31, 2012 | Regular Geek

  • http://davesquared.net David Tchepak

    I asked on the #haskell.au IRC group and got another approach to converting binary to int (from m3ga). Need to import Numeric, Data.Char, and Data.Maybe (if you want to handle errors with Maybe, otherwise can use non-total list functions like `head`).

        ghci> let fromBin = readInt 2 (`elem` “01”) digitToInt
        ghci> fromBin “100”
    [(4,"")]

    The `2` is the base we want, and the next arg is whether we want to parse a character. That gives us [(Int, String)], where the String is any unparsed characters. We can convert this to a Maybe Int with:

        ghci> let fromBin’ = listToMaybe . map fst . readInt 2 (`elem` “01”) digitToInt
        ghci> fromBin’ “100”
        Just 4

    Depending on how you want to handle odd inputs, you may want to check the second part of the tuple to ensure there are no unparsed characters left before returning the parsed int.

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