Java results differ for (int)Math.pow(2,x) and 1<<x

Question

Why do the following two operations yield different results in Java for x = 31 or 32 but the same results for x=3?

int x=3;
int b = (int) Math.pow(2,x);
int c = 1<<x;

Results:

x=32: b=2147483647; c=1;
x=31: b=2147483647; c=-2147483648;
x=3:  b=8         ; c=8

Answer 1

Here's a micro-benchmark for the case of a long. On my laptop (2.8GHz), using shift instead of Math.pow is over 7x faster.

int limit = 50_000_000;
@Test
public void testPower() {
    Random r = new Random(7);
    long t = System.currentTimeMillis();
    for (int i = 0; i < limit; i++) {
        int p = r.nextInt(63);
        long l = (long)Math.pow(2,p);
    }
    long t1 = System.currentTimeMillis();
    System.out.println((t1-t)/1000.0); // 3.758 s
}
@Test
public void testShift() {
    Random r = new Random(7);
    long t = System.currentTimeMillis();
    for (int i = 0; i < limit; i++) {
        int p = r.nextInt(63);
        long l = 1L << p;
    }
    long t1 = System.currentTimeMillis();
    System.out.println((t1-t)/1000.0); // 0.523 s
}

Answer 2

There are multiple issues at play:

• An int can only store values between -2147483648 and 2147483647.
• 1 << x only uses the lowest five bits of x. Thus, 1 << 32 is by definition the same as 1 << 0.
• Shift operations are performed on the two's-complement integer representation of the value of the left operand; this explains why 1 << 31 is negative.
• Math.pow(2, 32) returns a double.
• (int)(d), where d is a double greater than 2147483647 returns 2147483647 ("the largest representable value of type int").

What this interview question does is show that (int)Math.pow(2, x) and 1 << x are not equivalent for values of x outside the 0...30 range.

P.S. It is perhaps interesting to note that using long in place of int (and 1L in place of 1) would give yet another set of results different from the other two. This holds even if the final results are converted to int.