2

我想知道以下哪一项对于获取整数 x 的第 i 个最右边的位更快，其中 i 从 0 开始：

x & (1 << i)
x >> i % 2

也很好奇为什么一个更快。

谢谢！

4

2 回答 2

9

笔记

正如所评论的，这取决于许多因素。另外，你不应该在意。在任何真正的程序中，我相信您不会关心如此低级的细节。过早的优化是对时间的可怕浪费。

此外，除非您的相等概念只是零/非零的概念，否则这些不是相等的操作。

但这是一个有趣的练习

将 GCC 与 -O3 一起使用并反汇编我看到：

x & (1 << i)

The first version
Dump of assembler code for function op1:
   0x0000000000000000 <+0>:     mov    %esi,%ecx
   0x0000000000000002 <+2>:     mov    $0x1,%eax
   0x0000000000000007 <+7>:     shl    %cl,%eax
   0x0000000000000009 <+9>:     and    %edi,%eax
   0x000000000000000b <+11>:    retq   
End of assembler dump.

和

x >> i % 2

Dump of assembler code for function op2:
   0x0000000000000010 <+0>:     mov    %esi,%ecx
   0x0000000000000012 <+2>:     sar    %cl,%edi
   0x0000000000000014 <+4>:     mov    %edi,%edx
   0x0000000000000016 <+6>:     shr    $0x1f,%edx
   0x0000000000000019 <+9>:     lea    (%rdi,%rdx,1),%eax
   0x000000000000001c <+12>:    and    $0x1,%eax
   0x000000000000001f <+15>:    sub    %edx,%eax
   0x0000000000000021 <+17>:    retq

所以这是 a shift leftand an andvs a shift right, load effective address, and anand操作。在这个硬件上似乎很明显什么会更快，但除非你在一个微控制器上，否则看起来很明显的东西通常并不那么清楚。让我们测试一下。

我对（内联）操作进行了大约一千万次调用的循环，并确保返回操作结果的总和，这样编译器就不会全部丢弃。

[tommd@mavlo Test]$ gcc -O3 so.c -o so
[tommd@mavlo Test]$ time ./so

real    0m0.388s
user    0m0.384s
sys     0m0.003s
[tommd@mavlo Test]$ time ./so

real    0m0.384s
user    0m0.380s
sys     0m0.003s
[tommd@mavlo Test]$ vi so.c  // I changed the function to the second one
[tommd@mavlo Test]$ gcc -O3 so.c -o so
[tommd@mavlo Test]$ time ./so

real    0m0.380s
user    0m0.377s
sys     0m0.002s
[tommd@mavlo Test]$ time ./so

real    0m0.380s
user    0m0.379s

好吧，完全一样。现代超级缩放器处理器中有足够的硬件来隐藏任何差异。

于 2012-06-30T22:58:12.033 回答
6

提取位的惯用方法是

(x >> i) & 1

这也可以类似地工作不止一位，或者

x & (1 << i)

如果您只想测试一个位。

请注意，在 C 中x不能为负数（最好声明为无符号），并且如果x比 an 长，int您需要指定 1 在第二个中也是那么长。

使用%会使读者感到困惑，并且性能可能会更差，具体取决于编译器。

于 2012-07-01T05:56:18.977 回答