def multiply(x, y, k):
    """multiply two integers x and y, where k >= 0 is a power of 2,
        and k is at least as large as the maximum number of bits in x or y"""
       
    if k == 1:
        return x * y
    
    k_over_two = k // 2  # simply shifts the bits one to the right.
        
    two_to_the_k_over_two = 1 << k_over_two
    
    xL, xR = x // two_to_the_k_over_two, x % two_to_the_k_over_two
    yL, yR = y // two_to_the_k_over_two, y % two_to_the_k_over_two
    # note that these two operations could be done by bit shifts and masking.
    
    p1 = multiply (xL,    yL,    k_over_two)
    p2 = multiply (xL+xR, yL+yR, k_over_two)
    p3 = multiply (xR,    yR,    k_over_two) 
    
    return (p1 << k) + ((p2 - p3 - p1) << k_over_two) + p3
    
print (multiply(1000, 1000, 16))