division and multiplication by power of 2

Question

I read in a paper that division and multiplication of a number by a power of 2 is a trivial process. I have searched a lot of internet for the explanation but doesn't get it. Can any one explain in easy words what does this actually meant to say.

Answer 1

It is trivial from the bit operations perspective. Multiplying by 2 is equivalent to a shift left by 1 bit, division is a right shift. similarly it is the same trivial to multiply and divide by any power of 2.

int a = 123;           // or in binary format: a = 0b01111011;

assert (a * 2) == (a << 1);   // 2 = 2^1, (a << 1) = 11110110
assert (a / 2) == (a >> 1);   // 2 = 2^1, (a >> 1) = 00111101

assert (a * 8) == (a << 3);   // 8 = 2^3, (a << 3) = 1111011000
assert (a / 8) == (a >> 3);   // 8 = 2^3, (a >> 3) = 0000001111

Also note that a*2 = a+a, and addition is sometimes even cheaper than shifting, depending on the hardware.

For signed division, beware that in some languages (such as C), integer division truncates towards zero, while arithmetic right shift (shifting in copies of the sign bit for 2's complement) always rounds towards -Infinity. e.g. (-5)/2 == -2, but (-5) >> 1 == -3. Implementing signed division by 2 can still be done with a shift + extra operations to add the sign bit to get the truncation behaviour. (Look at C compiler output.)

Answer 2

Since all numbers are stored in binary a multiplication/division is a simple bit-shift operation.

For example (multiplication):

• 5 = 101 (binary)
• 5 * 2 = 10 = 1010 (binary) - just shifted all bits 1 position to the left
• 5 * 4 = 20 = 10100 (binary) - just shifted all bits 2 positions to the left

The same applies to the division (right bit-shift operation), but you need to consider the carry for odd number divisions if you need the remainder.