Programming Praxis – Bit Hacks

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
About these ads

Tags: , , , , , , , ,

3 Responses to “Programming Praxis – Bit Hacks”

  1. programmingpraxis Says:

    That business of unchecked arithmetic producing the wrong answer is the thing that most annoys me in C and other low-level languages.

  2. Remco Niemeijer Says:

    @programmingpraxis: I don’t think this is a problem of low-level languages so much as a problem of only having a limited number of bits. Since abs(minBound) cannot be expressed in 32 bits, your only options are to either loop back around or to throw an exception. Sure, on occasion the second one might be nice to detect the problem occuring, but most of the time you’ll prefer the speed of the first alternative (never mind the practical problems of, for example, throwing an exception when the overflow occurs in a shader executed on the graphics card rather than in the code itself).
    There is ofcourse the solution of using an Integer/BigInt/etc. datatype, but that can also cause a significant performance drop.
    Does Scheme have checked arithmetic on fixed-size numbers? Because I don’t recall ever working with a language that did.

    • programmingpraxis Says:

      In Scheme, it depends on the implementation. All of the big implementations automatically switch to big integers. Since Scheme historically hasn’t had bit operations (they were added in the last version of the Standard, about forty years late), bit operations are done “arithmetically” as if the variables involved held numbers instead of bits, so instead of wrapping around Scheme just adds more bits.

      However, all of the big implementations also offer non-Standard fixed-width integer data types, so they can interoperate with other languages, and those data types work the same way as they work everywhere else.

      My comment was about bits, but also about arithmetic in general. In C, you have to be very careful to avoid overflow; most programs aren’t careful enough, and bad bugs are the result. In Scheme, I can ignore the problem and trust the language to do the right thing.

      We had an exercise about that recently on Programming Praxis: how to perform modular multiplication when the intermediate result can overflow. You will recall that we solved the problem for most, but not all, situations, though I did mention how to solve the problem in the remaining case. The problem is that the code to solve the problem in full gets really messy, and slows things down for the normal case.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: