在特殊情况下:是和快于%？

Question

我看到了这篇文章的选择答案.

我很惊讶,(x & 255) == (x % 256)如果x是无符号整数,我想知道总是%用&in x % nfor 替换是否有意义,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;
}

将编译(由GCC 6.2与-O3; Clang 3.9生成非常相似的代码)到:

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是不同的,因为

如果乘法,除法或模数表达式的两个操作数具有相同的符号,则结果为正.否则,结果是否定的.模数运算符号的结果是实现定义的.

和AFAICT,大多数实现决定模数表达式的结果总是与第一个操作数的符号相同.请参阅此文档.

因此,mod_signed优化(来自nwellnhof的评论):

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

从逻辑上讲,我们可以证明i % 256 == i & 255对于所有无符号整数,我们可以信任编译器来完成它的工作.