此快捷方式以常数（C）取模是否有效？ IF（A mod 2 ^ n）> C：{-C}

Question

希望做模运算符，A mod K，...

• K是uint32_t常数，不是2的幂，我将一遍又一遍地使用它。
• A是uint32_t变量，可能比K大〜2 ^ 13倍。
• ISA没有单周期模或除法指令。 （8位微型）

幼稚的方法似乎与幼稚的分裂方法相吻合；重复减法直到下溢，然后保留余数。显然，这在最坏情况下的性能会很差，但适用于任何A和K。

Aknown fast approach对于K的幂为2的幂很好用，是逻辑与，且幂为2 -1。

来自Wikipedia ...A % 2^n == A & (2^n - 1)

我的膝关节反应是将这两件事一起使用，我想知道这是否有效？

具体来说，我认为我可以使用两个mod的技巧来缩小上述减法的最坏情况。换句话说，快速修改至比我的常数高2的最接近的幂，然后在必要时减去我的常数。这是实际问题中的代码，已完全扩展。

A = A AND 2^n # 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 havecheckedthe usualplaces。我想念什么？

Answer 1

您不能同时使用两种方法。首先了解为什么以下等式成立。

A % p == A & (p - 1), where p = 2^n

p将在其二进制表示形式中确切地具有1设置位，例如其位置为x。

所以所有在x位置上具有至少一个置位的数字都可以由p整除。

但是当p不是2的幂时不是这种情况。

如果那没有道理，请举例：

A = 18 = 10010,
K = 6 = 110,
A % K = 0

根据您的方法，将对AND和A执行7 (= 2^3-1)操作，导致2，这是错误的。