一些方法包括:
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))
基本上,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]
也许有更好(更短?更快?)的方法,鉴于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]
%timeit [mod_c2py(a, b) for a, b in ll]
需要注意的是,mod_c2py()
只能帮助我们了解从 mod_c()
函数中可以期望的性能。
(编辑以修复一些提出的方法并包含一些计时)
(编辑-2 添加了解决方案 mod_c5()
)
(编辑-3 添加解决方案 mod_c6()
到 mod_c9()
)
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))
。 - norok2k & ...
就变得多余了。 - norok2b * (x|1)
可以简化为:-b if a ^ b < 0 else b
。 - norok2k
写错了,你发现得真好。我把它保留为b * (x|1)
是因为我想避免条件语句。但那也是一个好的解决方案。 - ArborealAnole