division and multiplication by power of 2

问题:

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.

回答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.)

回答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.

回答3:

Important in this context is that division by 2 (or by a power of 2) is trivial only for integer arithmetic. It gets less trivial when you're talking about floating point division.

The reason for that is that division by the base number of some numeral system (binary, octal, hexadecimal, you name it) can always be done by a simple right shift of the number.

For example, in the decimal system with division by ten you have:

230.0 / 10.0 = 23.00 

(shift the decimal point one position to the left, which translates to a right shift of the number)

The same for hexadecimal numbers:

0xA2FF / 0x10 = 0xA2F 

(number shifted one position to the right)

And the same for binary numbers:

1101011 / 10 = 110101 (binary notation)
107     /  2 = 53     (decimal notation for the same equation)

If you want to divide by a power of two, the number of right shifts you need to perform corresponds to the exponent. For example, division by 4 means division by 2*2, equals two right shift operations:

1101011 / 100 = 11010 (binary notation, two shift operations)
107     /   4 = 26    (decimal notation)

回答4:

Basically to multiply and divide a number for a power of 2, if the number is expressed in binary, you just need to translate all the binary digit left or right:

00100 that is 4, if you want to multiply for 2*2*2 you just translate all the number left 3 times:

100000 that is exaqctly 32 (4 * 8 = 32)

to devide it's the other way around