# Multiply, or shift bits?

• 03-15-2011, 05:48 PM
plm-pusik
Multiply, or shift bits?
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
• 03-15-2011, 06:18 PM
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.
• 03-15-2011, 06:36 PM
Iron Lion
The difference seems to be negligible. I tested it with this:
Code:

```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:

Code:

```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.
• 03-15-2011, 07:05 PM
JosAH
Quote:

Originally Posted by Iron Lion
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
• 03-15-2011, 10:08 PM
plm-pusik
Quote:

Originally Posted by Iron Lion
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.

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