views:

79

answers:

3

I am working through a problem which i was able to solve, all but for the last piece - i am not sure how can one do multiplication using bitwise operators:

0*8 = 0

1*8 = 8

2*8 = 16

3*8 = 24

4*8 = 32

Can you please recommend an approach to solve this?

+3  A: 

To multiply by 2 to the power of N (i.e. 2^N) shift the bits N times to the left

0000 0001 = 1 

times 4 = (2^2 => N = 2) = 2 bit shift : 0000 0100 = 4

times 8 = (2^3 -> N = 3) = 3 bit shift : 0010 0000 = 32

etc..

To divide shift the bits to the right.

The bits are whole 1 or 0 - you can't shift by a part of a bit thus if the number you're multiplying by is does not factor a whole value of N ie. 17 = 16 + 1 = 2^4 + 1

this to multiply by 17 you have to do a 4 bit shit to the left, and then add the original number again:

a = 0000 0011 = 2 

times 16 = (2^4 => N = 2) = 4 bit shift : 0001 1000 = 24

+ the number (0000 0001)

ie.

    0001 1000  (48)  
+   0000 0011   (3)
=============
    0001 1111  (51)
Preet Sangha
right. it's not quite the same thing though. what if you want to multiply 3*17
mac
yes I miswrote left and right lol
Preet Sangha
+2  A: 

I believe this should be a left shift. 8 is 2^3, so left shift 3 bits:

2 << 3 = 8

adrift
Brilliant. Thank you
mac
A: 

You'd factor the multiplicand into powers of 2.
3*17 = 3*(16+1) = 3*16 + 3*1 ... = 0011b << 4 + 0011b

Phil