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

## No comments:

## Post a Comment