Bit Hacks

August 9, 2013

A time-honored tradition among programmers is to hack a program to reduce the number of operations it takes, and a major component of that effort goes in to bit hacks, which we can define as dealing with data structures smaller than a single byte. Embedded systems programmers use bit hacks all of the time, as do game programmers and many others. We have three tasks today:

1) Determine the sign of an integer.

2) Determine if two integers have the same sign.

3) Determine the absolute value of an integer without branching.

Your task is to write bit hacks for the three tasks noted above; you may want to find multiple solutions for some of them. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

6 Responses to “Bit Hacks”

  1. […] today’s Programming Praxis exercise, our goal is to write three functions that use bit twiddling, namely […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/08/09/programming-praxis-bit-hacks/ for a version with comments):

    import Data.Bits
    import Data.Composition
    
    negative :: Int -> Bool
    negative n = testBit n (bitSize n - 1)
    
    sameSign :: Int -> Int -> Bool
    sameSign = (not . negative) .: xor
    
    absolute :: Int -> Int
    absolute n = xor (n + mask) mask where mask = shiftR n (bitSize n - 1)
    
  3. phil said

    1) if 1<<32 & int < int return "positive"
    2) if int ^ int < 1<<32 return True
    3) (1<<32 -1) & int

  4. Graham said

    My same_sign isn’t that imaginative, but if you have a sign function that
    returns -1, 0, or 1, then abs(n) is just sign(n) * n. Is multiplication more
    expensive than branching? Though I’ve written a decent amount of C++, I tend
    to use it as a reasonably high-level language; I’m somewhat ruined when it
    comes to bit-hackery.

    #include <array>
    #include <iostream>
    
    auto sign(intmax_t n) -> intmax_t { return (n > 0) - (n < 0); }
    auto same_sign(intmax_t m, intmax_t n) -> bool { return sign(m) == sign(n); }
    auto abs(intmax_t n) -> intmax_t { return sign(n) * n; }
    
    auto main() -> int
    {
        std::array<intmax_t, 3> ns{-17, 0, 17};
        std::cout << std::boolalpha;
        for (auto n : ns) {
            std::cout << "sign(" << n << ") = " << sign(n) << std::endl;
        }
        for (auto m : ns) {
            for (auto n: ns) {
                std::cout << "sign(" << m << ") == sign(" << n <<")?\t" <<
                    same_sign(m, n) << std::endl;
            }
        }
        for (auto n : ns) {
            std::cout << "|" << n << "| = " << abs(n) << std::endl;
        }
    }
    
  5. brooknovak said

    Here is a C# solution.
    Note that .NET uses two’s complement for signed integers.
    At first glance the Abs function looks a little wrong, but in .Net the right shift operator ignores the highest order bit, this “isNegative” will be either 0 or -1.

    public static class BitHacks
    {
    	private const int IntegerMSBMask = 1 << 31;
    
    	public static bool IsPositive(int n) {
    		return (IntegerMSBMask & n) == 0;
    	}
    
    	public static bool HasSameSign(int a, int b) {
    		return (IntegerMSBMask & a) == (IntegerMSBMask & b);
    	}
    
    	/// <summary>
    	/// Absolute math function.
    	/// </summary>
    	/// <param name="n">Can be any integer except Int.MinValue</param>
    	public static int Abs(int n) {
    		int isNegative = (n & IntegerMSBMask) >> 31;
    		int isPositive = (~isNegative) & 1;
    		int sign = (1 * isPositive) + isNegative;
    		return n * sign;
    	}
    }
    
  6. brooknovak said

    Woops! I left a redundant multiplication of 1 in the posted code for Abs! lol.

    int sign = ((n & IntegerMSBMask) >> 31) + ((~isNegative) & 1);
    [/sourecode]

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 630 other followers

%d bloggers like this: