Some bit twiddling functions explained

Introduction

Using clever bitwise arithmetic, it is possible to implement some useful functions in a short amount of code, without using expensive loops or branches (if-statements). Here I will give a some bit twiddling functions and justify why they are correct.

Some quick notes for those who are not familiar with Java but are familiar with at least one other programming language:

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. 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 type int, we have ~x == (x ^ 0xFFFFFFFF). By the definition of two’s complement arithmetic, -x == ((~x) + 1) == ~(x - 1). With y == 0xFFFFFFFF, we have (x + y) ^ y == ~(x + (-1)) == ~(x - 1) == -x.

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.

Sign function

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

The sign function (also called signum) indicates whether a number x is less that 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:

Determine if number is a power of 2

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 integeral power of 2. Now consider two cases: