leetcode-BitOperations

常见的数字之间的运算法则

1
2
3
4
5
6
7
# 进位和余位问题，模拟进位相加法，以为10进制为例
res = (num + add) // 10 # 如果使用同一个add，这res在前，因为add会在第二步被更新
add = (num + add) % 10

# int相除，向上取整
res = ceil(x, y)
res = (x + y - 1) // y

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 求x，y的最大公约数
# 短除法，
def func1(a,b):
    res=1
    for i in range(2,min(a,b)):
        while(a % i == 0 and b % i == 0):
            res*=i
            a/=i
            b/=i
    return res

# 辗转相除法，
def func2(num1, num2):
    m = max(num1, num2)
    n = min(num1, num2)
    r = m % n
    while r != 0:
        m = n
        n = r
        r = m % n
    return r

最小公倍数

1
2
3
4
5
6
# 求x，y的最小公倍数
# 两数之积(s) = 最小公倍数(a) * 最大公约数(b)

s = abs(x * y)
b = func(num1, num2)
a = s // b