Results 1 to 5 of 5
  1. #1
    plm-pusik is offline Member
    Join Date
    Aug 2010
    Posts
    17
    Rep Power
    0

    Default 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 05:54 PM.

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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. #3
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    4

    Default

    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 06:39 PM.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,437
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by Iron Lion View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    plm-pusik is offline Member
    Join Date
    Aug 2010
    Posts
    17
    Rep Power
    0

    Default

    Quote Originally Posted by Iron Lion View Post
    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

Similar Threads

  1. Bitshifting doesn't shift bits?
    By Skiller in forum New To Java
    Replies: 19
    Last Post: 03-02-2011, 09:30 AM
  2. matrix multiply
    By slixtrix in forum New To Java
    Replies: 8
    Last Post: 09-13-2010, 06:50 AM
  3. multiply two matrixes
    By smart princess in forum New To Java
    Replies: 8
    Last Post: 12-06-2009, 06:43 PM
  4. display column value multiply with 100
    By tiiim83 in forum JavaServer Pages (JSP) and JSTL
    Replies: 0
    Last Post: 01-15-2009, 03:40 AM
  5. How to multiply two matrices
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-14-2008, 08:50 PM

Posting Permissions

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