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