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 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:
The syntax for statements and expressions is essentially the same as that in C, C++, C#, JavaScript, etc.
The
inttype is a 32-bit signed two’s complement integer type.Integer overflow is silent and well-defined.
The
>>operator means signed (arithmetic) right shift. The>>>operator 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. 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 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, thenx >> 31 == 0,-x == 0,(-x) >>> 31 == 0, and finally(0 | 0) == 0.If
x > 0, then the top bit (bit #31) is 0, thusx >> 31 == binary 00...00 == 0.-x == -1 == binary 11...11.(-x) >>> 31 == binary 00...001 == 1. Finally,(0 | 1) == 1.If
x < 0, then the top bit (bit #31) is 1, thusx >> 31 == binary 11...11 == 0xFFFFFFFF == -1.-x == 1.(-x) >>> 31 == 0. Finally,(-1 | 0) == -1.
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 integral power of 2. Now consider two cases:
If
xis a power of 2, thenxhas a leftmost 1 followed by zero or more 0s. Withx == binary 1 (n 0s), we know thatx - 1 == binary 0 (n 1s). Since inxandx - 1the 1s are in different positions, their bitwise conjunction is zero:(x & (x - 1)) == 0.If
x > 0andxis not a power of 2, thenxhas a leftmost 1 and some other 1 to the right of it. Note thatxhas 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, whereddddare zero or more digits of any value. Thenx - 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.
