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).