modulo 的常量 (C) 快捷方式是否有效？ IF (A mod 2^n) > C: { -C}
Is this shortcut for modulo by a constant (C) valid? IF (A mod 2^n) > C: { -C}
正在寻找 modulo 运算符，A mod K 其中...
- K 是一个 uint32_t 常数，不是 2 的幂，我会一遍又一遍地使用它。
- A 是一个 uint32_t 变量，可能比 K 大 ~2^13 倍。
- ISA 没有单周期modulo 或除法指令。 （8 位微型）
幼稚的方法似乎与幼稚的除法方法不谋而合；重复减法直到下溢，然后保留余数。这显然会有相当糟糕的最坏情况性能，但适用于任何 A 和 K。
A known fast approach 对 K 来说效果很好，它是 2 的某个幂 ，是逻辑与与 2 的幂 -1。
来自维基百科...
A % 2^n == A & (2^n - 1)
我的下意识反应是同时使用这两个东西，我想知道这是否有效？
具体来说，我认为我可以使用两个 mod 技巧的幂来缩小上述减法方法的最坏情况。换句话说，快速 mod 到我的常量 以上最接近的二的幂，然后在必要时减去我的常量。这是实际问题中的代码，已完全展开。
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 的 2 的幂应该总是使 2K 更大。也就是说，K < 2^n < 2K 意味着我应该只需要一个额外的测试，然后可能需要一个减法。
...但这似乎太简单了。如果它有效，我希望以前见过它。但我找不到例子。我也找不到反例。 I have checked the usual places。我错过了什么？
您不能将这两种方法结合起来。首先理解为什么下面的等式成立。
A % p == A & (p - 1), where p = 2^n
p 将在其二进制表示中精确设置 1 位，假设其位置为 x。
所以所有在大于x的位置至少有一个设置位的数字都可以被p整除，这就是为什么用[=18=执行AND ] 将给出小于 2^x 的所有设置位，这与执行 mod
相同
但当 p 不是 2 的幂时，情况就不一样了。
如果这没有意义，那么举个例子：
A = 18 = 10010,
K = 6 = 110,
A % K = 0
按照你的做法，你会对A和7 (= 2^3-1)进行AND运算，得到2，这不是[=27=的值].
正在寻找 modulo 运算符，A mod K 其中...
- K 是一个 uint32_t 常数，不是 2 的幂，我会一遍又一遍地使用它。
- A 是一个 uint32_t 变量，可能比 K 大 ~2^13 倍。
- ISA 没有单周期modulo 或除法指令。 （8 位微型）
幼稚的方法似乎与幼稚的除法方法不谋而合；重复减法直到下溢，然后保留余数。这显然会有相当糟糕的最坏情况性能，但适用于任何 A 和 K。
A known fast approach 对 K 来说效果很好，它是 2 的某个幂 ，是逻辑与与 2 的幂 -1。
来自维基百科...
A % 2^n == A & (2^n - 1)
我的下意识反应是同时使用这两个东西，我想知道这是否有效？
具体来说，我认为我可以使用两个 mod 技巧的幂来缩小上述减法方法的最坏情况。换句话说，快速 mod 到我的常量 以上最接近的二的幂，然后在必要时减去我的常量。这是实际问题中的代码，已完全展开。
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 的 2 的幂应该总是使 2K 更大。也就是说，K < 2^n < 2K 意味着我应该只需要一个额外的测试，然后可能需要一个减法。
...但这似乎太简单了。如果它有效，我希望以前见过它。但我找不到例子。我也找不到反例。 I have checked the usual places。我错过了什么？
您不能将这两种方法结合起来。首先理解为什么下面的等式成立。
A % p == A & (p - 1), where p = 2^n
p 将在其二进制表示中精确设置 1 位，假设其位置为 x。
所以所有在大于x的位置至少有一个设置位的数字都可以被p整除，这就是为什么用[=18=执行AND ] 将给出小于 2^x 的所有设置位，这与执行 mod
但当 p 不是 2 的幂时，情况就不一样了。
如果这没有意义，那么举个例子：
A = 18 = 10010,
K = 6 = 110,
A % K = 0
按照你的做法，你会对A和7 (= 2^3-1)进行AND运算，得到2，这不是[=27=的值].