def mul(n,m): # compute n*m; n and m are nonnegative integers
a = n
b = m
c = 0
# invariant ab+c = nm
while a != 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
return c