如何计算余数有什么不同之处吗？

Question

假设a = 2^k，int c = b%a和int c = b & (a-1)在性能和正确性方面有区别吗？

- Hossein

---

假设您的意思是unsigned int c，并且b和a都是unsigned int，并且编译器已知变量a的值，并且您已打开了优化器，则不会出现问题。如果上述任何条件不成立，则可能会出现问题。 - zwol

取决于编译器是否能够证明a = 2^k。如果可以，那么它可能能够为两个片段生成相同的汇编代码。如果不能，那么第二个片段通常会更快（因为除法通常是一项非常昂贵的操作）。 - user3386109

即使编译器可以证明a = 2^k，它也不应该为两个表达式生成相同的汇编代码。 -1％16的结果是-1，但-1＆15的结果是15（使用二进制补码表示）。 - Eric Postpischil

@EricPostpischil 是的，我的评论是作为zwol的补充，而不是替代。如果a或b中有任意一个是负数，则第二个代码片段具有未定义或实现定义的行为，因此不应使用。 - user3386109

Answer 1

对于二进制补码的整数和 a （2 的幂次方），当且仅当 b 是非负数或 a 的倍数时，b%a 等于 b & a-1。因此，编译器只有在知道 b 是非负数或者是 a 的倍数时，才能将 b%a 替换为 b & a-1（在后一种情况下，应该将表达式替换为零）。在当前典型的处理器上，与和减法指令至少与求余（除法）指令一样快，而且经常更快，因此推荐使用 b & a-1，如果程序员知道条件被满足，除非他们确信编译器会为 b%a 生成 AND，或者他们还想要商 b/a。（如果需要商，则编译器必须生成除法指令，并且处理器通常会提供余数和商）。

当然，编译器可以通过将其设置为 unsigned int 来确保 b 是非负数。除非 a 是一个常数，否则保证编译器知道 a 是 2 的幂次方就比较复杂。

- Eric Postpischil

---

我想编译器可以关注一个 assert(1==__builtin_popcount(a))（如果它理解GCC内置函数）或 assert(a && !(a&(a-1)))，即使断言被禁用... - jxh