Multiply, or shift bits?

[plm-pusik]

Hey, just a quicky!

Let's say I have a program that needs to be fast, and let's say that I want to multiply/divide something with a power of two (2^1, 2^2, ...). Would it be faster to carry out the multiplication, for example n * 2, or would it be faster to shift the bits one step to the left, n << 1? Or makes it no difference?


-PLM

[pbrockway2]

I have no idea what the solution is. But I'll post anyway... Because the solution is easy enough to find: compile your program twice using both approaches, test and time.

The JLS just says (15.19 Shift Operators) "The value of n<<s is n left-shifted s bit positions; this is equivalent (even if overflow occurs) to multiplication by two to the power s". And I don't think the JVM specification says anything about a difference in implementation on which you can rely.

In practice I would write the expression in whatever form seemed most natural. This is subjective, of course, and what "natural" means would depend on the result of testing your and similar code.

[Iron Lion]

The difference seems to be negligible. I tested it with this:

public class ShiftVsMultiply {
	public static void main(String[] args) {
		long t = System.currentTimeMillis();
		int j;
		for (int i = 0; i <= 500000000; i++) {
			j = i * 2;
		}
		System.out.println("Time taken for *2: " + (System.currentTimeMillis() - t) + "ms");
		t = System.currentTimeMillis();
		for (int i = 0; i <= 500000000; i++) {
			j = i << 1;
		}
		System.out.println("Time taken for <<1: " + (System.currentTimeMillis() - t) + "ms");
	}
}

The output:

Time taken for *2: 379ms
Time taken for <<1: 373ms

However, using bitwise AND as an alternative to modding by a power of 2 (for example, (x & 7) instead of (x % 8)) is about 27 times faster.

[JosAH]

However, using bitwise AND as an alternative to modding by a power of 2 (for example, (x & 7) instead of (x % 8)) is about 27 times faster.

Which is quite strange because Aho, Hopcroft and Ullman already showed that integer division is as fast as multiplication (big-oh wise speaking).

kind regards,

Jos

[plm-pusik]

However, using bitwise AND as an alternative to modding by a power of 2 (for example, (x & 7) instead of (x % 8)) is about 27 times faster.

I didn't know about this, but it makes sense when you think about it.

Wouldn't it be better if the compiler replaced our power of 2 multiplications/divisions with bit shifts and our modulus with the bitwise AND operator? Considering they actually are slightly faster.


-PLM