是i =(i + 1)&3比i =(i + 1)%4快

Question

我正在优化c ++代码.在一个关键步骤,我想实现以下功能y=f(x):

f(0)=1

f(1)=2

f(2)=3

f(3)=0

哪一个更快？使用查找表或 i=(i+1)&3 或 i=(i+1)%4？或者更好的建议？

Answer 1

几乎可以肯定,查找表将是最慢的.在很多情况下,编译器会为(i+1)&3和生成相同的程序集(i+1)%4; 但是,根据i的类型/签名,它们可能不是严格等同的,编译器将无法进行优化.例如代码

int foo(int i)
{
    return (i+1)%4;
}

unsigned bar(unsigned i)
{
    return (i+1)%4;
}

在我的系统上,gcc -O2生成:

0000000000000000 <foo>:
   0:   8d 47 01                lea    0x1(%rdi),%eax
   3:   89 c2                   mov    %eax,%edx
   5:   c1 fa 1f                sar    $0x1f,%edx
   8:   c1 ea 1e                shr    $0x1e,%edx
   b:   01 d0                   add    %edx,%eax
   d:   83 e0 03                and    $0x3,%eax
  10:   29 d0                   sub    %edx,%eax
  12:   c3                      retq   

0000000000000020 <bar>:
  20:   8d 47 01                lea    0x1(%rdi),%eax
  23:   83 e0 03                and    $0x3,%eax
  26:   c3                      retq

因为你可以看到因为有关有符号模数结果的规则(i+1)%4,所以首先会产生更多的代码.

最重要的是,(i+1)&3如果表达你想要的东西,你可能最好使用该版本,因为编译器做一些你不期望的事情的机会较少.

Answer 2

我不会讨论过早优化.但答案是他们的速度会相同.

任何理智的编译器都会将它们编译成同样的东西.无论如何,除以2的幂的除法/模数将被优化为按位运算.

因此,使用您找到的(或其他人会发现的)更具可读性.

编辑:正如罗兰所指出的那样,它有时会根据符号表现不同:

未签名&:

int main(void)
{
    unsigned x;
    cin >> x;
    x = (x + 1) & 3;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, 3
push    eax

无符号模数:

int main(void)
{
    unsigned x;
    cin >> x;
    x = (x + 1) % 4;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, 3
push    eax

签 &:

int main(void)
{
    int x;
    cin >> x;
    x = (x + 1) & 3;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, 3
push    eax

签名模数:

int main(void)
{
    int x;
    cin >> x;
    x = (x + 1) % 4;
    cout << x;

    return 0;
}

mov eax, DWORD PTR _x$[ebp]
inc eax
and eax, -2147483645            ; 80000003H
jns SHORT $LN3@main
dec eax
or  eax, -4                 ; fffffffcH

Answer 3

很有可能,您不会发现任何差异:任何合理的现代编译器都知道将两者优化为相同的代码.