Thread: multiplication using bit operation

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    25

    multiplication using bit operation

    Hi

    If I need to multiply a number by 2, I can left shift the number by 1 bit.
    because shifting left by n bits on a signed or unsigned binary number
    has the effect of multiplying it by 2^n (base 2 and power n).
    Now if I want to multiple by 3, how can write a C program using bit operations.

    please comment

    thanks & regards
    Onebrother
    Last edited by onebrother; 02-21-2008 at 04:58 AM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    230
    I don't know how, but I don't think it'll be as simple as 2^n. Why would you want to do this anyways?
    I might not be a pro, but I'm usually right

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You can do that - if you want to make it generic, you will have to do something that checks if the lowest bit of the first multiplicand is 1, add the second multiplicand to the product, then shift the first multiplicand right, and the second multiplicand left.

    So for example 10 * 5 = (10 + (10 << 2)).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    Very very nice question indeed... Actually you would probably implement it with a shift and add.
    If x was the number to multiply by 3, then:
    (x<<1)+x is your answer.
    The problem is if you can not use arithmetic addition, as bitwise operators can't replace addition i think, except if you use something like... masking all 32 bits and xoring them one bye one? But that would be much slower than the original addition no? And a mess code too.
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

  5. #5
    Registered User
    Join Date
    Mar 2007
    Posts
    25
    Quote Originally Posted by xuftugulus View Post
    Very very nice question indeed... Actually you would probably implement it with a shift and add.
    If x was the number to multiply by 3, then:
    (x<<1)+x is your answer.
    The problem is if you can not use arithmetic addition, as bitwise operators can't replace addition i think, except if you use something like... masking all 32 bits and xoring them one bye one? But that would be much slower than the original addition no? And a mess code too.

    thanks for your reply...

    what is the equivalent bit operation if I want to divide a number
    by 3, as right shift of a number by n bits is equivalent of dividing it by 2^n.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    what is the equivalent bit operation if I want to divide a number
    by 3, as right shift of a number by n bits is equivalent of dividing it by 2^n.
    I think you may have to implement a division algorithm yourself, like what xuftugulus mentioned about implementing addition in general with bitwise operators.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Mar 2007
    Posts
    25
    multiplying x by 3 using bit operation in general as you explained is

    (x<<1) + x

    But say if I want to multiply (x=) 3 by 5 then how this will work?

    because left shifting 3 by 1 bit will result 6 & adding 3 to it will be 9 only. It
    does not become 15.

    please comment

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    But say if I want to multiply (x=) 3 by 5 then how this will work?
    (5 << 1) + 5 = 10 + 5 = 15

    As you noted, the formula works for multiply by 3, not multiply by 5.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Hint: 5 == 4 + 1

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by onebrother View Post
    Hi

    If I need to multiply a number by 2, I can left shift the number by 1 bit.
    because shifting left by n bits on a signed or unsigned binary number
    has the effect of multiplying it by 2^n (base 2 and power n).
    Now if I want to multiple by 3, how can write a C program using bit operations.

    please comment

    thanks & regards
    Onebrother
    Forgetting basic math? If you have a method of multiplying by two, then you can multiply by three, because 3 * x = 2 * x + x... Right?

    Quote Originally Posted by onebrother View Post
    But say if I want to multiply (x=) 3 by 5 then how this will work?
    How about 5 * x = 4 * x + x? Figure out how to multiply by 4 with a shift.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 32 bit to 64 bit Ubuntu
    By Akkernight in forum Tech Board
    Replies: 15
    Last Post: 11-17-2008, 03:14 AM
  2. hexadecimal bit operation
    By vlrk in forum C Programming
    Replies: 2
    Last Post: 10-17-2008, 10:04 AM
  3. Replies: 7
    Last Post: 12-10-2004, 08:18 AM
  4. 32 bit floating point multiplication
    By HelpMePlease in forum C Programming
    Replies: 1
    Last Post: 11-30-2004, 08:39 AM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM