Multiplying an unsigned integer by 10 with limited bitwise operators

Question

This is a question on a practice exam:

Write a function that multiples the argument by 10. You may only use these operators: << - & ^ and the only allowed constants to shift by are 1 2 4 8 16.

The function prototype is:

unsigned int(unsigned int x);

We were given a solution, which was:

unsigned int(unsigned int x) { 
    return (x << 4) - (x << 2) - (x << 1); 
} 

I understand that it works, and that it does so by subtracting multiples of ten from an integer. I don't understand why it works, and would like to understand the process of how to arrive at this answer.

Thanks in advance for any answers!

Answer 1

(x << 4) is essentially x * 16, (x << 2) is x * 4, and (x << 1) is x * 2. Therefore, 16x - 4x - 2x = 10x.

As for why (x << 4) is equal to x * 16, it's because of the binary representation. Let's take 10 in binary (only 8 bits shown for clarity; there's actually a bunch more zeroes to the left):

00001010

Now let's shift left 4 spaces:

10100000

That's 160.

A way of thinking of this is that when you add a zero in base ten (i.e. 10 -> 100), you're multiplying by 10. When you add a zero in base two, you're multiplying by 2. Therefore, shifting 4 spaces (and therefore adding 4 zeroes) multiplies by 2*2*2*2 = 16.