与更易读的方法相比,c ++中的Bitwise XOR的效率

Question

我最近为我正在研究的一个研究项目编写了一些代码,效率非常重要.我一直在考虑使用一些常规方法来处理并使用按位XOR代替.我想知道的是,如果有差异(如果我执行此操作说数百万次),或者如果我使用03 in g ++后它是相同的话.

想到的两个例子:

我有一个实例(我正在使用纯正的整数)如果n是奇数,我需要将n改为n-1或者如果n是偶数,则需要将n改为n +(n + 1).我想我有几个选择:

if(n%2) // or (n%2==0) and flip the order
    n=n-1
else
    n=n+1

要么

n=n+2*n%2-1; //This of course was silly, but was the only non-bitwise 1 line I could come up with

最后:

n=n^1;

所有这些方法显然都做同样的事情,但我的感觉是第三种方法效率最高.

下一个例子是更一般的说明.假设我正在比较两个正整数,其中一个会比其他整数表现更好.或者即使我执行此操作数百万次,差异也不会明显:

if(n_1==n_2)
if(! (n_1 ^ n_2) )
if( n_1 ^ n_2) else \do work here

编译器是否会在所有这些实例中执行相同的操作？我只是好奇是否有一个实例我应该使用按位操作而不相信编译器为我做的工作.

修正:正确的问题陈述.

Answer 1

它很容易检查,只需启动你的反汇编程序.看一看:

FC:

unsigned int f1(unsigned int n)
{
  n ^= 1;  
  return n;
}

unsigned int f2(unsigned int n)
{
  if (n % 2)
    n=n-1;
  else
    n=n+1;

  return n;
}

建造和拆解:

$ cc -O3 -c f.c 
$ otool -tV f.o 
f.o:
(__TEXT,__text) section
_f1:
00  pushq   %rbp
01  movq    %rsp,%rbp
04  xorl    $0x01,%edi
07  movl    %edi,%eax
09  leave
0a  ret
0b  nopl    _f1(%rax,%rax)
_f2:
10  pushq   %rbp
11  movq    %rsp,%rbp
14  leal    0xff(%rdi),%eax
17  leal    0x01(%rdi),%edx
1a  andl    $0x01,%edi
1d  cmovel  %edx,%eax
20  leave
21  ret

它看起来f1()有点短,无论现实中的问题是否取决于某些基准测试.

Answer 2

我有点不同意这里的大多数答案，这就是为什么我仍然看到自己在回答 2010 年的问题:-)

实际上，XOR 是 CPU 可能执行的最快操作，好的一点是所有 CPU 都支持它。原因很简单：只需 4 个 NAND 门或 5 个 NOR 门即可创建异或门 - 这意味着使用硅结构可以轻松创建。毫不奇怪，我所知道的所有 CPU 都可以在 1 个时钟周期（甚至更少）内执行 XOR 操作。

如果您需要对数组中的多个项目进行异或，现代 x64 CPU 也支持同时对多个项目进行异或，例如 f.ex。Intel 上的 SIMD 指令。

您选择的替代解决方案使用 if-then-else。确实，大多数编译器都能够解决这个简单的问题......但是为什么要冒险呢？结果是什么？

编译器无法弄清楚的结果是分支预测错误。单个分支预测失败很容易需要 17 个时钟周期。如果您看一下处理器指令的执行速度，您会发现分支对您的性能非常不利，尤其是在处理随机数据时。

请注意，这也意味着如果您错误地构建了测试，数据将扰乱您的性能测量。

所以总结一下：首先思考，然后编程，然后分析——而不是相反。并使用异或。