## 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

### 6 Responses to “Bit Hacks”

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

```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) {
}

/// <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]