## 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 11101111_{b}. The mask is `w >> 7`

, which has a value of -1 and is stored as 11111111_{b}. Then `w + mask`

is -17 + -1 = -18, which is stored in two’s complement as 11101110_{b}, and the logical-and of that number and `mask`

is 00010001_{b}, 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.

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

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

1) if 1<<32 & int < int return "positive"

2) if int ^ int < 1<<32 return True

3) (1<<32 -1) & int

My same_sign isn’t that imaginative, but if you have a

`sign`

function thatreturns -1, 0, or 1, then

`abs(n)`

is just`sign(n) * n`

. Is multiplication moreexpensive 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.

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.

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

…

int sign = ((n & IntegerMSBMask) >> 31) + ((~isNegative) & 1);

[/sourecode]

…