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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
6 Comments »

6 Responses to “Bit Hacks”

  1. Programming Praxis – Bit Hacks | Bonsai Code said
    August 9, 2013 at 11:28 AM

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

  2. Remco Niemeijer said
    August 9, 2013 at 11:28 AM

    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
    August 9, 2013 at 4:59 PM

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

  4. Graham said
    August 10, 2013 at 12:08 AM

    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
    August 28, 2013 at 9:23 AM

    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
    August 28, 2013 at 9:26 AM

    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 comment