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)

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

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