c++ - 特殊情况: Is & faster than %?

Question

我看到了被选中的answer对此post .

我很惊讶 (x & 255) == (x % 256) 如果 x 是无符号整数，我想知道总是替换 % 是否有意义& in x % n for n = 2^a (a = [1, ...]) 和 x 是一个正整数.

因为这是我作为人类可以决定的特殊情况，因为我知道程序将处理哪些值而编译器不处理。 如果我的程序使用大量模运算，我能否获得显着的性能提升？

当然，我可以编译并查看反汇编。但这只会回答我对一个编译器/架构的问题。我想知道这在原则上是否更快。

Answer 1

如果你的整数类型是无符号的，编译器会对其进行优化，结果是一样的。如果它已签名，则有所不同...

这个程序:

int mod_signed(int i) {
  return i % 256;
}
int and_signed(int i) {
  return i & 255;
}
unsigned mod_unsigned(unsigned int i) {
  return i % 256;
}
unsigned and_unsigned(unsigned int i) {
  return i & 255;
}

将被编译(by GCC 6.2 with -O3; Clang 3.9 produces very similar code)成:

mod_signed(int):
        mov     edx, edi
        sar     edx, 31
        shr     edx, 24
        lea     eax, [rdi+rdx]
        movzx   eax, al
        sub     eax, edx
        ret
and_signed(int):
        movzx   eax, dil
        ret
mod_unsigned(unsigned int):
        movzx   eax, dil
        ret
and_unsigned(unsigned int):
        movzx   eax, dil
        ret

mod_signed 的结果汇编不同，因为

If both operands to a multiplication, division, or modulus expression have the same sign, the result is positive. Otherwise, the result is negative. The result of a modulus operation's sign is implementation-defined.

和 AFAICT，大多数实现决定模数表达式的结果始终与第一个操作数的符号相同。见 this documentation .

因此，mod_signed 被优化为(来自 nwellnhof 的评论):

int d = i < 0 ? 255 : 0;
return ((i + d) & 255) - d;

---

从逻辑上讲，我们可以证明 i % 256 == i & 255 对于所有无符号整数，因此，我们可以相信编译器会完成它的工作。