Bit Hacks

August 9, 2013

I’ll admit that I’m not very good at bit hacking; too many years of programming in a high-level language like Scheme robs me of that ability. We’ll work in C instead of Scheme, because twiddling bits in Scheme is just too painful to contemplate.

1) Determine the sign of an integer: We didn’t specify how the result is to be given, so we have several different solutions:

int v; // task is to find the sign of v
int sign; // the desired result
// CHARBIT is the number of bits per byte, normally 8

sign = v < 0; // 1 if v is negative, else 0
sign = -(v >> (sizeof(int) * CHARBIT - 1)); // 1 if v is negative, else 0
sign = (v > 0) - (v < 0); // -1 if v is negative, +1 if v is positive, else 0

2) Determine if two integers have the same sign: We use logical-and to combine the bits of the two numbers; if the sign bits are the same, the result of the logical-and will be positive, otherwise it will be negative:

int x, y; // input values to compare signs

bool f = ((x ^ y) < 0); // 1 if x and y have opposite signs, else 0

3) Determine the absolute value of an integer without branching: The obvious way to find the absolute value of w is (w < 0) ? -w : w. But in modern CPUs, branches can kill performance, so we want to avoid branching. We need to change the value of the most significant bit of the integer to 0; here are two options:

int w; // we want to find the absolute value of w
unsigned int r; // the result goes here
int const mask = w >> sizeof(int) * CHAR_BIT - 1;

r = (w + mask) ^ mask;
r = (w ^ mask) - mask; // patented 2000 in USA

In the first solution, if w is positive, mask is 0, and both the addition and the logical-and leave w unchanged. That’s easy. Negative numbers are harder. Let’s take integers as being 8-bits long, and consider the example of abs(-17). In two’s complement, -17 is stored as 11101111b. The mask is w >> 7, which has a value of -1 and is stored as 11111111b. Then w + mask is -17 + -1 = -18, which is stored in two’s complement as 11101110b, and the logical-and of that number and mask is 00010001b, which is +17. If you don’t often look at bit representations of numbers, that makes your head spin.

The second solution is similar, but backwards.

You can run all these programs at http://programmingpraxis.codepad.org/WX1UsfmI.

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

%d bloggers like this: