使用Python的%运算符计算C语言中的%？

Question

我该如何使用Python的%运算符来计算C语言中的%运算符？ 两者之间的区别在于它们处理负值参数的方式不同。

在两种语言中，%被定义为满足以下关系（其中//是整数除法）的运算符：

a // b * b + a % b == a

但在C和Python中，a // b的舍入方式不同，导致对于a % b的定义不同。

例如，在C中（其中整数除法是使用int操作数的/运算符），我们有：

int a = 31;
int b = -3;
a / b;  // -10
a % b;  // 1

Python中的while循环：

a = 31
b = -3
a // b  # -11
a % b  # -2

我知道这个问题，回答的是相反的情况（即如何从C语言的%计算Python的%），并包含了其他讨论。

我也知道Python 3.7的math模块引入了remainder()函数，但其结果是一个float而不是int，因此它不能享受任意精度。

- norok2

Answer 1

一些方法包括：

def mod_c0(a, b):
    if b < 0:
        b = -b
    return -1 * (-a % b) if a < 0 else a % b

def mod_c1(a, b):
    return (-1 if a < 0 else 1) * ((a if a > 0 else -a) % (b if b > 0 else -b))

def mod_c2(a, b):
    return (-1 if a < 0 else 1) * (abs(a) % abs(b))

def mod_c3(a, b):
    r = a % b
    return (r - b) if (a < 0) != (b < 0) and r != 0 else r

def mod_c4(a, b):
    r = a % b
    return (r - b) if (a * b < 0) and r != 0 else r

def mod_c5(a, b):
    return a % (-b if a ^ b < 0 else b)

def mod_c6(a, b):
    a_xor_b = a ^ b
    n = a_xor_b.bit_length()
    x = a_xor_b >> n
    return a % (b * (x | 1))

def mod_c7(a, b):
    a_xor_b = a ^ b
    n = a_xor_b.bit_length()
    x = a_xor_b >> n
    return a % ((-b & x) | (b & ~x))

def mod_c8(a, b):
    q, r = divmod(a, b)
    if (a >= 0) != (b >= 0) and r:
        q += 1
    return a - q * b

def mod_c9(a, b):
    if a >= 0:
        if b >= 0:
            return a % b
        else:
            return a % -b
    else:
        if b >= 0:
            return -(-a % b)
        else:
            return a % b

所有工作都如预期一样，例如：

print(mod_c0(31, -3))
# 1

基本上，mod_c0() 实现了一个优化版本的 mod_c1() 和 mod_c2()，两者完全相同，只是在 mod_c1() 中，(相对昂贵) 调用 abs() 方法被替换为具有相同语义的三元条件运算符。

mod_c3() 和 mod_c4() 尝试直接修正需要的 a % b 值。两者之间的区别在于它们如何检测参数的相反符号：(a < 0) != (b != 0) 与 a * b < 0。

mod_c5() 方法受到@ArborealAnole答案的启发，基本上使用位异或来正确处理情况，而mod_c6() 和mod_c7() 与@ArborealAnole答案相同，但使用自适应右移与int.bit_length()。

mod_c8() 方法使用经过校正的整数除法定义来修复模数值。mod_c9() 方法受到@NeverGoodEnough答案的启发，基本上采用完全条件方式处理。

---

覆盖所有符号情况：

vals = (3, -3, 31, -31)
s = '{:<{n}}' * 4
n = 14
print(s.format('a', 'b', 'mod(a, b)', 'mod_c(a, b)', n=n))
print(s.format(*(('-' * (n - 1),) * 4), n=n))
for a, b in itertools.product(vals, repeat=2):
    print(s.format(a, b, mod(a, b), mod_c0(a, b), n=n))

a             b             mod(a, b)     mod_c(a, b)   
------------- ------------- ------------- ------------- 
3             3             0             0             
3             -3            0             0             
3             31            3             3             
3             -31           -28           3             
-3            3             0             0             
-3            -3            0             0             
-3            31            28            -3            
-3            -31           -3            -3            
31            3             1             1             
31            -3            -2            1             
31            31            0             0             
31            -31           0             0             
-31           3             2             -1            
-31           -3            -1            -1            
-31           31            0             0             
-31           -31           0             0             

更多的测试和基准测试：

import itertools


n = 100
l = [x for x in range(-n, n + 1)]
ll = [(a, b) for a, b in itertools.product(l, repeat=2) if b]


funcs = mod_c0, mod_c1, mod_c2, mod_c3, mod_c4, mod_c5, mod_c6, mod_c7, mod_c8, mod_c9
for func in funcs:
    correct = all(func(a, b) == funcs[0](a, b) for a, b in ll)
    print(f"{func.__name__}  correct:{correct}  ", end="")
    %timeit -n 8 -r 8 [func(a, b) for a, b in ll]
# mod_c0  correct:True  8 loops, best of 8: 9.67 ms per loop
# mod_c1  correct:True  8 loops, best of 8: 11.1 ms per loop
# mod_c2  correct:True  8 loops, best of 8: 12.3 ms per loop
# mod_c3  correct:True  8 loops, best of 8: 10.3 ms per loop
# mod_c4  correct:True  8 loops, best of 8: 10 ms per loop
# mod_c5  correct:True  8 loops, best of 8: 10.1 ms per loop
# mod_c6  correct:True  8 loops, best of 8: 17.1 ms per loop
# mod_c7  correct:True  8 loops, best of 8: 20.3 ms per loop
# mod_c8  correct:True  8 loops, best of 8: 15.8 ms per loop
# mod_c9  correct:True  8 loops, best of 8: 9.29 ms per loop

也许有更好（更短？更快？）的方法，鉴于Python使用C的%实现似乎更简单：

((a % b) + b) % b

为了了解C语言风格的“%”计算（上文中的“mod_c*（）”函数）与通常使用的“%”或获取Python风格的“%”所需的操作之间有何差异，请参考以下内容：

def mod_py(a, b):
    return a % b

def mod_c2py(a, b):
    return ((a % b) + b) % b


%timeit [mod_py(a, b) for a, b in ll]
# 100 loops, best of 3: 5.85 ms per loop
%timeit [mod_c2py(a, b) for a, b in ll]
# 100 loops, best of 3: 7.84 ms per loop

需要注意的是，mod_c2py() 只能帮助我们了解从 mod_c() 函数中可以期望的性能。

---

(编辑以修复一些提出的方法并包含一些计时)

(编辑-2 添加了解决方案 mod_c5())

(编辑-3 添加解决方案 mod_c6() 到 mod_c9())

- norok2

Answer 2

我在跟进@norok2的非常全面的答案。我已经尝试了使用分支的超级幼稚方法，似乎略微但一直更快（约为2-4%）。

def mod_naive(x,y):
  if y < 0:
    if x < 0:
      return x%y
    else:
      return (x%-y)
  else:
    if x < 0:
      return -(-x%y)
    else:
      return x%y

或者使用lambda表达式（不影响速度，只是更酷炫）：

mod_naive = lambda x,y: (x%y if x < 0 else x%-y) if y < 0 else (-(-x%y) if x < 0 else x%y)

与@norok2的最快解决方案（mod_c0）相比：

mod_c0 correct: True
100 loops, best of 3: 6.86 ms per loop

mod_naive correct: True
100 loops, best of 3: 6.58 ms per loop

我（天真）猜测的原因是分支预测算法最终会产生更少的总操作。

- NeverGoodEnough

Answer 3

对于64位整数，以下任一方式均可：

def mod_c_AA0(a,b):
    x=(a^b)>>63
    return a % (b*(x|1))

def mod_c_AA1(a,b):
    x=(a^b)>>63
    return a % ((-b & x)|(b & ~x))

使用二进制的补码。如norok2所建议的，将第一行替换为a_xor_b=a^b; x=a_xor_b>>a_xor_b.bit_length();，以便根据a和b的大小具有最佳位移特性。

- ArborealAnole

---

你可以用适当的 bit_length() 调用来替换硬编码数字，例如 def mod_c_xor(a, b): a_xor_b = a ^ b; x = a_xor_b >> a_xor_b.bit_length(); return a % (b * (x | 1))。 - norok2

此外，k & ... 就变得多余了。 - norok2

最后：b * (x|1) 可以简化为：-b if a ^ b < 0 else b。 - norok2

哎呀，k写错了，你发现得真好。我把它保留为b * (x|1)是因为我想避免条件语句。但那也是一个好的解决方案。 - ArborealAnole