Let's say we want to multiply 3 x 5 in binary:
Let's talk generally by substituting m x n (so here m = 3 and n = 5).
No matter what the value of m, we will end up by adding together a series of bit-shifted versions of n, here: 00101 and 01010
5 = 00101
3 = 00011 = 2**0 + 2**1
3 x 5 = (5 << 0) + (5 << 1)
For any m, we require the set of exponents i, j, k.. such that:
2**i + 2**j + 2**k + ... = m
[This has to be done from the "top down." First find the largest power of 2 that is less than m, record that exponent, and take m = m % 2**e to continue... It's tricky, and that's why I took the easy way out, below.]
Now we sum
n << i
+ n << j
+ n << k
+ ... = m x n
It's very helpful that Python will do bit-shifting on ints:
I spent a while debugging code to generate the needed exponents, before I decided to cheat (a bit) by using binary representation:
The first function below returns the exponents i,j,k...
The second does the bit-shifting. For efficiency, we do the factoring on the smaller of the two operands.