def multiply(x, y, n):
    """multiply two integers x and y, where n >= 0
       is a power of 2, and as large as the maximum number of bits in x or y"""
       
    if n == 1:
        return x * y
    
    n_over_two = n//2 
        
    two_to_the_n_over_two = 1 << n_over_two # a single right bit-shift

    
    xL, xR = x // two_to_the_n_over_two, x % two_to_the_n_over_two
    yL, yR = y // two_to_the_n_over_two, y % two_to_the_n_over_two
    # note that these two operations could be done by bit shifts and masking.
    
    p1 = multiply (xL, yL, n_over_two)
    p2 = multiply (xL, yR, n_over_two)
    p3 = multiply (xR, yL, n_over_two) 
    p4 = multiply (xR, yR, n_over_two)
    
    return (p1 << n) + ((p2 + p3) << n_over_two) + p4
    

print multiply((3000, 40000, 16))