def divide(x, y):
    """ Input: Two n-bit integers x and y, where y>=1.
        Output: The quotient and remainder when x is divided by y."""
    if x == 0:
        return 0, 0
    q, r = divide(x / 2, y)
    q, r = 2 * q, 2 * r
    if x % 2 == 1:
        r = r + 1
    if r >= y:
        q, r = q + 1, r - y
    return q, r

print divide(19, 4)
print divide(1445, 12)
print divide(4, 19)
print divide(76, 19)