## Posts Tagged ‘twiddling’

### Programming Praxis – Bit Hacks

August 9, 2013

In today’s Programming Praxis exercise, our goal is to write three functions that use bit twiddling, namely one to determine a numbers sign, one to determine of the signs of two numbers are equal and one to take the absolute value of a number without using branching. Let’s get started, shall we?

```import Data.Bits
import Data.Composition```

To determine whether or not a number is negative we can simply look at the highest bit.

```negative :: Int -> Bool
negative n = testBit n (bitSize n - 1)```

To check whether two numbers have the same sign we use an xor operation, which will produce a 0 in the highest bit when they are the same and a 1 when they’re not. We then test that bit to produce the result.

```sameSign :: Int -> Int -> Bool
sameSign = (not . negative) .: xor```

For the absolute function I used the provided algorithm. When testing I thought I’d found a mistake since abs(minBound) was not equal to maxBound. Turns out this is correct behaviour: minBound is equal to -2147483648, whereas maxBound is equal to 2147483647. Note the difference in the last number. Taking the absolute of minBound produces a value that cannot be expressed in 32 bits and thus loops right back around to minBound.

```absolute :: Int -> Int
absolute n = xor (n + mask) mask where mask = shiftR n (bitSize n - 1)```

Some tests to see if everything is working properly:

```main :: IO ()
main = do print \$       negative minBound
print \$       negative (-100)
print \$       negative   (-1)
print \$ not \$ negative     0
print \$ not \$ negative     1
print \$ not \$ negative   100
print \$ not \$ negative maxBound
print \$       sameSign minBound minBound
print \$       sameSign (-1) (-1)
print \$ not \$ sameSign (-1)   1
print \$ not \$ sameSign   1  (-1)
print \$       sameSign   1    1
print \$       sameSign maxBound maxBound
print \$ absolute minBound == minBound
print \$ absolute   (-100) ==      100
print \$ absolute       0  ==        0
print \$ absolute     100  ==      100
print \$ absolute maxBound == maxBound```