这个由常量(C)构成的模的快捷方式有效吗？若(A mod 2^n) > C：{ -C}
提问于 2019-12-26 02:06:04
想做模运算符，A mod K .
- K是一个uint32_t常数，不是2的幂，我会一次又一次地使用它。
- A是一个uint32_t变量，可能比K大2^13倍。
- ISA没有单周期模块或除法指令。(8位微)
朴素的方法似乎与朴素的除法一致；重复减法直到下流，然后保持其余的。这显然会有相当糟糕的情况下的表现，但对任何A和K。
一个已知快速方法，它能很好地工作在一个K上，它是2的幂，是逻辑的，它的幂是2 -1。
从维基百科..。A % 2^n == A & (2^n - 1)
我的膝跳反应是把这两件事结合起来，我想知道这是否有效？
具体来说，我想我可以使用两个mod技巧的力量缩小最坏的情况，对上述减法。换句话说，如果有必要的话，快速地把我的常数减到最接近我常量的2的幂。下面是实际问题中的代码，完全扩展了。
A = A AND (2^n - 1) # MOD A to the next higher power of two
if A > K: # See if we are still larger than our constant
A -= K # If so, subtract. We now must be lower.
##################
# A = A MOD K ???
##################在检查时，这应该总是有效的，而且应该总是快速的，因为下一个大于K的二次方应该总是这样，2K会更大。也就是说，K < 2^n < 2K意味着我只需要进行一次额外的测试，然后可能需要一次减法。
...but，这似乎太简单了。如果成功的话，我想我以前也见过。但我找不到一个例子。不过我也找不到反例。我有过 已选中 一如既往 地点.我遗漏了什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-12-26 02:47:18
你不能把这两种方法结合起来。首先要理解为什么下面的公式是正确的。
A % p == A & (p - 1), where p = 2^np的二进制表示中将有确切的1设置位，比如它的位置是x。
因此，在大于x的位置上至少有一个集合位的所有数字都可以被p整除，这就是为什么用p-1执行AND会给出比2^x更少的设置位，这与执行mod相同。
但是，当p不是2的强大力量时，情况就不是这样了。
如果这没有意义，那就举个例子：
A = 18 = 10010,
K = 6 = 110,
A % K = 0根据您的方法，您将使用A和7 (= 2^3-1)执行A操作，从而生成2，这不是MOD的值。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59486817
复制相关文章
点击加载更多
腾讯云开发者
