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.

Answer 2

x << 1 = x * 2.

x << 2 = x * 4.

x << 4 = x * 16.

16 - 4 - 2 = 10.

You could also use:

x << 3 = x * 8

But 8 + 2 = 10, so you could use (x << 2 << 1) + (x << 1).