def mul(n,m): # compute n*m; n and m are nonnegative integers, with n < 2^32
k = 32
a = n
b = m
c = 0
# invariant ab+c = nm and a < 2^k
while k != 0:
if a&1 == 1:
# no need to do a = a - 1, because of later a=a>>1
c = c + b
# (a-1)b + (c+b) = ab -b + c + b = ab+c = nm
a = a>>1
b = b<<1
# (a/2)2b+c = ab+c = nm
k = k - 1
# since the previous a was < the previous 2^k,
# a/2 < 2^(k-1)
# (a-1)/2 < 2^(k-1)
# we know a < 2^0, so a=0, just like before
return c