## Monday, January 27, 2014

### Sneaky Bit-Based hack

I came across this bit of code in java.util.Random.nextInt and was impressed by its beauty:

if ((n & -n) == n)  // i.e., n is a power of 2

How does this work? Well, we have to look at how negative numbers are represented. Java uses two's compliment.

import static java.lang.Integer.toBinaryString;
import static java.lang.String.format;
.
.
public static void main(String[] args) {
for (int i = 0 ; i < 32 ; i++) {
System.out.println(format("%1\$4d ", i) + formattedBinaryString(i));
System.out.println(format("%1\$4d ", -i) + formattedBinaryString(-i));
}
}

private static String formattedBinaryString(int n) {
String binaryString = toBinaryString(n);
return format("%1\$32s", binaryString);
}

gives an output of:

0        0
0        0
1        1
-1 11111111
2       10
-2 11111110
3       11
-3 11111101
4      100
-4 11111100
5      101
-5 11111011
6      110
-6 11111010
7      111
-7 11111001
8     1000
-8 11111000
9     1001
-9 11110111
10     1010
-10 11110110
11     1011
-11 11110101
12     1100
-12 11110100
13     1101
-13 11110011
14     1110
-14 11110010
15     1111
-15 11110001
16    10000
-16 11110000

Now, there's many ways of working out the binary representation in your head. Here's two:

1. given -1 is 11111111 (truncated), find the difference between your negative number and take those 1s away. So, say you were thinking of -5, then then the difference is 4 (= -1 - (-5)), so take 100 from the binary representation of -1 (ie, the 3rd 1 from the left) and you get 11111011. Just as above.

2. Moving from left to right of the binary representation of the positive number, find the first 1. Leave that alone and continue but this time flipping 1s to 0s and 0s to 1s.

The upshot of this latter way of doing it is that only powers of 2 have one bit and it's unchanged when converting to negative numbers.

(NB, for completeness, this algorithm does not work for 0. The negative for 0 in two's compliment is the same as just 0).

This reminds me of a bit trick a neck-bearded UNIX friend told me. How do you swap the values of integers i and j without using any other variable? The answer involves XOR:

int i = 17, j =29;

i = j ^ i;
j = i ^ j;
i = j ^ i;

// now i = 29, j = 17