# Thread: Multiply, or shift bits?

1. Member
Join Date
Aug 2010
Posts
17
Rep Power
0

## 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
Last edited by plm-pusik; 03-15-2011 at 06:54 PM.

2. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,712
Rep Power
14
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.

3. Senior Member
Join Date
Nov 2010
Posts
210
Rep Power
6
The difference seems to be negligible. I tested it with this:
Java 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:

Java 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.
Last edited by Iron Lion; 03-15-2011 at 07:39 PM.

4. 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

5. Member
Join Date
Aug 2010
Posts
17
Rep Power
0
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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•