gcd.py

def gcd(x, y):
    if x < y:
        x, y = y, x
    
    two = 0
    while y > 0:
        if x & 1 == 0 and y & 1 == 0:
            two += 1
            x = x >> 1
            y = y >> 1
        elif x & 1 == 0:
            x = x >> 1
            if x < y:
                x, y = y, x
        elif y & 1 == 0:
            y = y >> 1
        else:
            x, y = x - y, y
            if x < y:
                x, y = y, x
    
    return x * 2 ** two