Programming Praxis

Bit Hacks

August 9, 2013 9:00 AM

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.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

6 Responses to “Bit Hacks”

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

By Programming Praxis – Bit Hacks | Bonsai Code on 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)

By Remco Niemeijer on August 9, 2013 at 11:28 AM

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

By phil on August 9, 2013 at 4:59 PM

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;
    }
}

By Graham on August 10, 2013 at 12:08 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;
	}
}

By brooknovak on August 28, 2013 at 9:23 AM

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

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

By brooknovak on August 28, 2013 at 9:26 AM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

Bit Hacks

Share this:

Related

6 Responses to “Bit Hacks”

Leave a Reply