Menu
How can I multiply and divide using only bit shifting and adding?
372
To multiply a number, a binary shift moves all the digits in the binary number along to the left and fills the gaps after the shift with 0: to multiply by two, all digits shift one place to the left. to multiply by four, all digits shift two places to the left.
The right shift operator shifts the bits towards the right. This means it does the exact opposite of the left shift operator i.e. every time we shift a number towards the right by 1 bit it divides that number by 2.
Binary Multiply. Repeated shift and add - starting with a result of 0, shift the second multiplicand to correspond with each 1 in the first multiplicand and add to the result. Shifting each position left is equivalent to multiplying by 2, just as in decimal representation a shift left is equivalent to multiplying by 10 ...
To multiply in terms of adding and shifting you want to decompose one of the numbers by powers of two, like so:
21 * 5 = 10101_2 * 101_2 (Initial step) = 10101_2 * (1 * 2^2 + 0 * 2^1 + 1 * 2^0) = 10101_2 * 2^2 + 10101_2 * 2^0 = 10101_2 << 2 + 10101_2 << 0 (Decomposed) = 10101_2 * 4 + 10101_2 * 1 = 10101_2 * 5 = 21 * 5 (Same as initial expression) (_2 means base 2)
As you can see, multiplication can be decomposed into adding and shifting and back again. This is also why multiplication takes longer than bit shifts or adding - it's O(n^2) rather than O(n) in the number of bits. Real computer systems (as opposed to theoretical computer systems) have a finite number of bits, so multiplication takes a constant multiple of time compared to addition and shifting. If I recall correctly, modern processors, if pipelined properly, can do multiplication just about as fast as addition, by messing with the utilization of the ALUs (arithmetic units) in the processor.
197
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
