Left Shift is Multiplication

Left-shift operator is the same as multiplication. So, if I = 3, then I << 1 is 6. How does that work? Let’s see.

2^3 + 2^2 = 8 + 4 = 12

2^4 + 2^3 = 16 + 8 = 24

Indeed, it multiplied the original value by 2. What happened here ?

We’ll, let’s multiply the first line by 2:

2 * (2^3 + 2^2) = 2^4 + 2^3.

Now it is clear that left-shifting means you’re multiply by two. If you left shift again, you’re multiply the original by 2^2, and so on.

If you want to multiply by a number that is not a power of two, say 17, then it would be something like this:

2^4 + 1 = 16 + 1

So you left-shift 4 times, and add the original number.

N * (2^4 + 1) = N(16 + 1) = (N << 4) + N


Converting Binary to Integer

I recently came across this example in my “Learning Python” book:

It converts a binary string to integer. The ord method is interesting, but I was interested in the algorithm itself. The algorithm says to look at the digits one by one, and each time through the loop, multiply the current value by 2 and add the next digit’s integer value. In this case, ‘1011’ would end up printing 13, which is correct. 13 in binary is 1011.

But then I struggled to think of how this would work. My naive solution would be to create a powers of two table, work my way from left to right, and get the highest value I can get without going over. For instance, 2^4 is 16, so I have to use 2^3, which is 8. Thus there is a bit in the 2^3 spot. Next I try 2^2, which is 4, and 8 + 4 is less than 13, so I can put a bit in the 2^2 spot. Then I try 2^1 which is 2, and 8 + 4 + 2 is 14, which is larger than 13, so there is a 0 in the 2^1 spot. And finally I need 2^0, as that is 1, and 8 + 4 + 1 = 13.

Since that was my solution, I would try to convert to code – because often times how you think about a solution is how you write it in code.

However, that was not what the book had. I now know what the book did.

Any integer can be represented in the form:

N is the integer, x_n is the number of digits depending on the base. So if it’s base 2 (binary), then it’s either 0 or 1. If it’s base 10, then it’s 0-9. q^n is going to be the base to the nth power. For binary, it’s going to be 2^n.

13 can be represented like this:

Now we can factor the 2 out, and keep factoring out the inner 2 until we can’t anymore:

We end up with the bottom form, which makes it easier to see why the original algorithm works. As a reminder, the original algorithm says multiply the current value by 2, and then add the next value. This is indeed what we do with (1), (2), and then (3).

So it all makes sense now! Yay!