Today I'll just reflect a bit about the next little piece of code
public static boolean isPowerOfTwo(int value){
return ((value & -value) == value)
}
The previous statement, surprisingly, computes a boolean value that holds the truth value regarding a certain value being or not power of two. If you're thinking something like what the fuck. I must tell that you're not alone. Been there, done that. Nevertheless this is a awesome piece of code. It is the fastest shortest and simplest (after understanding what is really happening) piece of code you could develop to check if a integer value is, indeed, a power of two. But, you ask, how this work. What is really happening here, what kind of wizardry is being deployed here? Nothing more than integer arithmetic and bitwise operations. You see, the integer representation when we are talking about computers is binary, additionally the arithmetic operations are done in the binary format. So when we add two numbers what is really happening is that we are doing a binary_add operation between a number A and B both in binary representation. Something like this
binary_add(010101010010,100010111010)
More, the binary_add operation must be such that all the semantics of integer numbers hold. So, for instance, if I've got a number a we know that the result of binary_add(a,-a) should be 0 which in binary is a 0000...000 with 32 or 64 zeros. To do this, there must be clever way of representing the binary numbers and the corresponding binary operations. And, indeed there is. The following program
public static void main(String[] args) {
for(int i=0;i<10;i++){
System.out.println(Integer.toBinaryString(i));
System.out.println(Integer.toBinaryString(-i));
}
}
will give you the binary representation of the first 10 integer numbers
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000001
11111111111111111111111111111111
00000000000000000000000000000010
11111111111111111111111111111110
00000000000000000000000000000011
11111111111111111111111111111101
00000000000000000000000000000100
11111111111111111111111111111100
00000000000000000000000000000101
11111111111111111111111111111011
00000000000000000000000000000110
11111111111111111111111111111010
00000000000000000000000000000111
11111111111111111111111111111001
00000000000000000000000000001000
11111111111111111111111111111000
00000000000000000000000000001001
11111111111111111111111111110111
We could go on and on, but I think that with only this first ten numbers we can find a very interesting pattern. First of all we should notice that for all those pairs of numbers the binary_add operation should hold allways the same result
00000000000000000000000000000000
Why's that? Well basically because a+(-a) should mean 0 right? So this first pattern is very easy to spot. Know we must understand what is that is being done inside the binary_add.
First we should notice a distinct binary pattern for positive and negative numbers. For positive numbers we've got
L1 B
where L1 is a variable number of leading zeros and B is the binary representation of the number
for the negative numbers we got
L2 B
where L2 is a variable number of leading one's and B is, again, the binary representation of the number.
The binary add operation works as our primary add operation with integer numbers. We sum two binary columns and then propagate the reminder to the next column. You can apply this rule to all the previous pair of numbers and you'll see that will hold the expected value of 100000000000000000000000000000000. Noting that you'll have know 33 bits you must drop the leftmost bit and this mean that you'll end up with the value 00000000000000000000000000000000, which is, as expected the binary representation of the integer value of zero.
Now we just need to note one last pattern. All the power of two have the following representation
A 1 C
B 1 C
Where A is a variable number of leading zeros, B a variable number of leading ones and C sequence of zeros with cardinality (we represent cardinality with the symbol #)
#C = 32-(1+#A), where #A=#B
So now we just need to note that if H is a power of two then it is of the form A1C and then if we compute (H & -H), where & is the bitwise operator AND it is equivalent to compute
(A1C) & (B1C) = (A1C)
where:
A & B = A
1 & 1 = 1
C & C = C
Summing all up into one just little Java expression we got
((value & -value) == value)