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