How can I perform multiplication by 36 using bit-shifting? Isn't it only possible to multiply by powers of 2? For example:
unsigned x = 4; // binary 00000000 00000000 00000000 00001000
unsigned y = x << 3; // multiply by 8, resulting in binary 00000000 ... 00100000
Thanks!
You can't multiply by a non-power of 2 by bit shifting alone.
But you can break it down using addition and multiplication:
x * 36 = x * (32 + 4)
= (x * 32) + (x * 4)
Since 32 and 4 are powers of 2 (2^5 and 2^2 respectively), you can perform those as separate shifts and add the results.
You can't by bit-shifting alone. Bit-shifting a binary number can only multiply or divide by powers of 2, exactly as you say. Similarly, you can only multiply or divide a decimal number by powers of 10 by place-shifting (e.g. 3 can become 30, 300, 0.3, or 0.03, but never 0.02 or 99).
But you could break the 36 down into sums of powers of two.
That is, you can split 36 into 32 + 4, which is 2^5 + 2^2. By the verbiage you have used ("write code that uses shifts"), the only requirement is to use bit-shifting and it should be allowed to perform additional operations as long as this requirement is met.
That is,
x * 36 = x * (32 + 4) = 32x + 4x = (2^5)x + (2^2)x = (x << 5) + (x << 2)
With this understanding, the simplest implementation would then be to add the two shifted values:
int result = (x << 5) + (x << 2);
