# Some bit-twiddling functions explained

## Introduction

Using clever bitwise arithmetic, it’s possible to implement some useful arithmetic functions in a short amount of code without using expensive loops or branches (if-statements). Here I will give some bit-twiddling functions expressed in the Java programming language and give proofs to justify their correctness.

Some quick notes for those who are familiar with at least one other programming language but unfamiliar with the specifics of Java:

• The syntax for statements and expressions is essentially the same as that in C, C++, C#, JavaScript, etc.

• `int` is the signed 32-bit two’s complement integer type.

• Integer overflow is silent and well-defined (unlike C/C++).

• The `>>` operator means signed (arithmetic) right shift, and `>>>` means unsigned (logical) right shift.

## Absolute value

```int abs(int x) {
int y = x >> 31;
return (x + y) ^ y;
}```

The absolute value function is defined as abs(x) = x if x ≥ 0, otherwise abs(x) = −x.

How this implementation works is as follows: `y` is the sign bit of `x` replicated to all 32 bits. If `x >= 0`, then `y == 0`, and `(x + 0) ^ 0 == x`. Otherwise `x < 0`, which means bit #31 of `x` is 1, so `y == 0xFFFFFFFF`. By definition since `x` has the type `int`, we have `~x == (x ^ 0xFFFFFFFF)`. By the definition of two’s complement arithmetic, `-x == (~x) + 1 == ~(x - 1)`. With `y == -1`, we have `(x + y) ^ y == ~(x + (-1)) == ~(x - 1) == -x`.

The line of code containing `return` can be written equivalently as: `return (x ^ y) - y;`. The proof is left as an exercise to the reader.

Take note of one caveat: the most negative number, `Integer.MIN_VALUE` = −231 = −2147483648, does not have a positive counterpart. But this implementation gives `abs(Integer.MIN_VALUE) == Integer.MIN_VALUE` instead of throwing an exception, much like `Math.abs(int)`.

## Sign function

```int sign(int x) {
return (x >> 31) | ((-x) >>> 31);
}```

The sign function (also called signum) indicates whether a number x is less than zero, equal to zero, or greater than zero. By definition, sign(x) = −1 if x < 0, sign(0) = 0, and sign(x) = 1 if x > 0.

To show why this implementation of the sign function is correct, consider the three cases:

• If `x == 0`: Left side is `(x >> 31) == 0`. Right side is `-x == 0`, `((-x) >>> 31) == 0`. Finally, `(0 | 0) == 0`.

• If `x > 0`: Left side, the top bit (bit #31) is 0, so `(x >> 31) == 0`. Right side, the top bit of `-x` is 1, so `((-x) >>> 31) == 1`. Finally, `(0 | 1) == 1`.

• If `x < 0`: Left side, the top bit (bit #31) is 1, so `(x >> 31) == 0xFFFFFFFF == -1`. Right side, we can disregard the value. Finally, `(-1 | anything) == -1`.

## Power-of-2 test

```boolean isPowerOf2(int x) {
return x > 0 && (x & (x - 1)) == 0;
}```

This function returns `true` if `x == 1, 2, 4, 8, 16, ...` and `false` otherwise. To start, the condition `x > 0` excludes numbers that cannot possibly be a positive integral power of 2. Now consider two cases:

• If `x` is a power of 2, then `x` has a leftmost 1 followed by zero or more 0s. With `x == binary 1 (n 0s)`, we know that `x - 1 == binary 0 (n 1s)`. Since in `x` and `x - 1` the 1s are in different positions, their bitwise conjunction is zero: `(x & (x - 1)) == 0`.

• If `x > 0` and `x` is not a power of 2, then `x` has a leftmost 1 and some other 1 to the right of it. Note that `x` has a rightmost 1 (which is at a different position than its leftmost 1). So the number has a form: `x == binary 1 dddd 1 0...0`, where `dddd` represents zero or more digits of any value. Then `x - 1 == binary 1 dddd 0 1...1`, where the right part 10...0 turns into 01...1. The left part 1dddd is unchanged, thus `(x & (x - 1)) == binary 1 dddd 00...0 != 0`.