2

i が 0 から始まる整数 x の右端の i 番目のビットを取得するために、次のうちどれがより高速かを知りたいです。

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

また、なぜ1つが速いのかについても興味があります。

ありがとう！

4

2 に答える 2

9

ノート

コメントしたように、これは多くの要因に依存します。また、気にする必要はありません。実際のプログラムでは、このような低レベルの詳細について心配することはないと思います。時期尚早の最適化は恐ろしい時間の無駄です。

また、同等の概念がゼロ/非ゼロの概念のみでない限り、これらは同等の操作ではありません。

でも楽しい練習です

-O3 を指定して GCC を使用し、逆アセンブルすると、次のようになります。

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

つまり、shift leftとand対 、shift right、load effective addressおよびand操作です。このハードウェアでは何が高速になるかは明らかですが、マイクロコントローラーを使用していない限り、明らかと思われることはあまり明確ではないことがよくあります。テストしてみましょう。

(インライン化された) 操作に対して 1,000 万回の呼び出しのようなループを作成し、操作結果の合計を確実に返すようにして、コンパイラがすべてを破棄しないようにしました。

[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)

1ビットだけテストしたい場合。

xCでは負であってはならない (できれば符号なしで宣言する)xことに注意してくださいint。

を使用%すると、読者が混乱し、コンパイラによってはパフォーマンスが大幅に低下する可能性があります。

于 2012-07-01T05:56:18.977 に答える