python - 使用 Python 的 `%` 计算 C 的 `%` ？

Question

如何计算 C 的 %使用 Python 的 % ?
两者之间的区别在于它们处理否定论点的方式。

在这两种语言中，%以这种关系(// 是整数除法)的方式定义:

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

但 a // b 的四舍五入在 C 和 Python 中是不同的，导致 a % b 的定义不同。 .

例如，在 C 中(整数除法只是 / 和 int 操作数)我们有:

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

在 Python 中:

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

我知道这 question ，它解决了相反的问题(即如何从 C 的 % 计算 Python 的 %)并包含其他讨论。

我也知道 Python 3.7 math模块介绍 remainder() 但其结果是 float ，而不是 int因此它不会享有任意的精度。

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在需要的情况下具有值(value)。两者的区别在于它们如何检测参数的相反符号: (a < 0) != (b != 0)与 a * b < 0 相比. mod_c5()方法的灵感来自 @ArborealAnole's answer , 并且基本上使用按位异或来正确处理这些情况，而 mod_c6()和 mod_c7()与 @ArborealAnole's answer 相同但使用自适应右移 int.bit_length() . mod_c8()方法使用整数除法的更正定义来确定模值。 mod_c9()方法的灵感来自 @NeverGoodEnough's answer ，并且基本上是完全有条件的。

涵盖所有标志案例:

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             

更多测试和基准测试:

n = 100
k = 1
l = [x for x in range(-n, n + k, k)]
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(func.__name__, 'correct:', all_equal)
    %timeit [func(a, b) for a, b in ll]
    print()

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

mod_c1 correct: True
100 loops, best of 3: 7.86 ms per loop

mod_c2 correct: True
100 loops, best of 3: 8.49 ms per loop

mod_c3 correct: True
100 loops, best of 3: 7.56 ms per loop

mod_c4 correct: True
100 loops, best of 3: 7.5 ms per loop

mod_c5 correct: True
100 loops, best of 3: 7.94 ms per loop

mod_c6 correct: True
100 loops, best of 3: 13.4 ms per loop

mod_c7 correct: True
100 loops, best of 3: 16.8 ms per loop

mod_c8 correct: True
100 loops, best of 3: 12.4 ms per loop

mod_c9 correct: True
100 loops, best of 3: 6.48 ms per loop

考虑到 Python 的 % 的实现，也许有更好(更短？更快？)的方法。使用 C 的 %似乎更简单:

((a % b) + b) % b

感受一下 C 风格的 %计算(上面的 mod_c*() 函数)反对通常的 %或获取 Python 风格所需的操作 %来自 C :

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() 获得什么性能。功能。

( 已编辑 修复一些建议的方法并包括一些时间)
( EDITED-2 添加 mod_c5() 解决方案)
( EDITED-3 将 mod_c6() 添加到 mod_c9() 解决方案)