How to perform multiplication, using bitwise operators?
To multiply by any value of 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.
since: 17 = 16 + 1
thus: 17 = 2^4 + 1
therefore: x * 17 = (x * 16) + x in other words 17 x's
thus to multiply by 17 you have to do a 4 bit shift to the left, and then add the original number again:
==> x * 17 = (x * 16) + x
==> x * 17 = (x * 2^4) + x
==> x * 17 = (x shifted to left by 4 bits) + x
so let x = 3 = 0000 0011
times 16 = (2^4 => N = 4) = 4 bit shift : 0011 0000 = 48
plus the x (0000 0011)
ie.
0011 0000 (48)
+ 0000 0011 (3)
=============
0011 0011 (51)
Edit: Update to the original answer. Charles Petzold has written a fantastic book 'Code' that will explain all of this and more in the easiest of ways. I thoroughly recommend this.
To multiply two binary encoded numbers without a multiply instruction. It would be simple to iteratively add to reach the product.
unsigned int mult(x, y)
unsigned int x, y;
{
unsigned int reg = 0;
while(y--)
reg += x;
return reg;
}
Using bit operations, the characteristic of the data encoding can be exploited. As explained previously, a bit shift is the same as multiply by two. Using this an adder can be used on the powers of two.
// multiply two numbers with bit operations
unsigned int mult(x, y)
unsigned int x, y;
{
unsigned int reg = 0;
while (y != 0)
{
if (y & 1)
{
reg += x;
}
x <<= 1;
y >>= 1;
}
return reg;
}