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

问题:

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

回答1:

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.

回答2:

According to the documentation Math.pow will promote both of its arguments to double and return double. Obviously when the returned result is double and you cast it to int you'll get only the highest 32 bits and the rest will be truncated - hence you always get the (int) Math.pow(2,x); value. When you do bitshift you always work with ints and hence an overflow occurs.

回答3:

Consider the limits of the type int. How large a number can it hold?

回答4:

int is 32 bits in size and since it is signed (by default), the first bit is used for the sign. When you shift left 31 bits, you get the Two's Compliment, which is -(2^32). When you shift left 32 bits, it just loops all the way back around to 1. If you were to do this shifting with longs instead of ints, you would get the answers you expect (that is until you shift 63+ bits).

回答5:

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
}