c++ - num％2またはnum＆1を使用して、数値が偶数かどうかを確認しますか？

Question

ええと、与えられた数が偶数であるかどうかを決定する少なくとも2つの低レベルの方法があります：

 1. if (num%2 == 0) { /* even */ } 
 2. if ((num&1) == 0) { /* even */ }

私は2番目のオプションがはるかにエレガントで意味のあるものだと考えています。それは私が通常使用するものです。しかし、それは好みの問題だけではありません。実際のパフォーマンスは異なる場合があります。通常、ビット単位の演算（logialなど）は、mod（またはdiv）演算よりもはるかに効率的です。もちろん、とにかくそれを最適化できるコンパイラもあると主張するかもしれませんが、私は同意します...しかし、そうでないコンパイラもあります。

もう1つのポイントは、経験の浅いプログラマーにとっては、2番目のポイントを理解するのが少し難しいかもしれないということです。その上で、これらのプログラマーがこの種のステートメントを理解するのにその短い時間を費やす場合にのみ、おそらくすべての人に利益をもたらすだろうと私は答えます。

どう思いますか？

num指定された2つのスニペットは、がunsigned intであるか、2の補数表現の負の数である場合にのみ正しいです。-いくつかのコメントとして、かなりの状態です。

score 76 · Accepted Answer

私は最初に読みやすさのためにコーディングするので、ここでの私の選択はですnum % 2 == 0。これは、よりもはるかに明確ですnum & 1 == 0。コンパイラーに最適化について心配させ、プロファイリングでこれがボトルネックであることが示された場合にのみ調整します。それ以外は時期尚早です。

2番目のオプションははるかにエレガントで意味のあるものだと思います

私はこれに強く反対します。数値は、2を法とする合同がゼロであるためであり、2進表現が特定のビットで終了するためではありません。バイナリ表現は実装の詳細です。実装の詳細に依存することは、一般的にコードの臭いです。他の人が指摘しているように、LSBのテストは、1の補数表現を使用するマシンでは失敗します。

もう1つのポイントは、経験の浅いプログラマーにとっては、2番目のポイントを理解するのが少し難しいかもしれないということです。その上で、これらのプログラマーがこの種のステートメントを理解するのにその短い時間を費やす場合にのみ、おそらくすべての人に利益をもたらすだろうと私は答えます。

同意しません。意図を明確にするために、全員がコーディングする必要があります。均一性をテストしている場合、コードはそれを表現する必要があります（コメントは不要である必要があります）。繰り返しますが、2を法とする合同性をテストすることは、LSBをチェックするよりもコードの意図をより明確に表現します。

そして、さらに重要なことに、詳細はメソッドに隠されている必要がありますisEven。したがって、の定義で1回if(isEven(someNumber)) { // details }だけ表示する必要があります。num % 2 == 0isEven

score 24 · Accepted Answer

一部のコンパイラが最適化しないと言う場合は、一部のコンパイラが%2符号付き整数に1の補数表現を使用することにも注意する必要があります。その表現では、負の数に対して&1 間違った答えを与えます。

では、何が必要ですか？「一部のコンパイラ」では遅いコード、または「一部のコンパイラ」では間違っているコードですか？いずれの場合も同じコンパイラである必要はありませんが、どちらの種類も非常にまれです。

もちろん、numが符号なし型、またはC99固定幅整数型の1つ（int8_t2の補数である必要があるなど）の場合、これは問題ではありません。その場合、私は%2よりエレガントで意味のあるもので&1あり、パフォーマンスのために時々必要になるかもしれないハックであると考えています。たとえば、CPythonはこの最適化を行わないと思います。完全に解釈された言語についても同じことが言えます（ただし、解析のオーバーヘッドにより、2つのマシン命令の違いが小さくなる可能性があります）。ただし、CまたはC ++コンパイラーが可能な限りそれを行わなかったのに出くわしたのは少し驚きです。なぜなら、それは以前でなければ命令を出す時点では簡単だからです。

一般に、C ++では、コンパイラーの最適化機能に完全に翻弄されていると言えます。標準のコンテナーとアルゴリズムにはnレベルの間接参照があり、コンパイラーがインライン化と最適化を完了すると、そのほとんどが消えます。まともなC++コンパイラは朝食前に定数値で算術演算を処理でき、まともでないC++コンパイラは何をしてもゴミコードを生成します。

score 12 · Accepted Answer

パフォーマンスに関するあなたの結論は、人気のある誤った前提に基づいています。

何らかの理由で、言語操作を「明らかな」マシンの対応物に翻訳し、その翻訳に基づいてパフォーマンスの結論を出すことを主張します。&この特定のケースでは、ビット単位の演算とC ++言語の演算はビット単位の演算で実装する必要がありますが、モジュロ%演算には何らかの方法でマシンの除算が必要であると結論付けました。そのようなアプローチは、もしあれば、非常に限られた用途です。

まず、言語操作をそのような「文字通りの」方法で、つまり「同等の」マシン操作にマッピングすることによって解釈する実際のC++コンパイラーを想像することはできません。主な理由は、同等のマシン操作が単に存在しないと考えることが多いためです。

オペランドとして即値定数を使用するこのような基本的な操作に関しては、自尊心のあるコンパイラーは、整数の場合num & 1と両方がまったく同じことを行うことを常にすぐに「理解」します。これにより、コンパイラーは両方の式に対して完全に同一のコードを生成します。当然、パフォーマンスはまったく同じになります。num % 2num

ところで、これは「最適化」とは呼ばれていません。最適化とは、定義上、コンパイラーが、より効率的なコードを生成するために（プログラムの観察可能な動作を維持するために）、抽象C++マシンの標準的な動作から逸脱することを決定する場合です。この場合、偏差はありません。つまり、最適化はありません。

さらに、特定のマシンで両方を実装するための最適な方法は、ビット単位でも除算でもないが、他の専用のマシン固有の命令である可能性があります。その上、特定の値の偶数/奇数がプロセッサのステータスフラグなどを介して「無料で」公開される可能性があるため、命令がまったく必要ない可能性があります。それ。

つまり、効率の引数は無効です。

第二に、元の質問に戻るには、値の偶数/奇数を決定するためのより好ましい方法はnum % 2、必要なチェックを文字通り（「定義により」）実装し、事実を明確に表現するため、確かにアプローチです。チェックは純粋に数学的なものです。つまり、（バリアントの場合のように）その表現のプロパティではなく、数値のプロパティに関心があることを明確にします。num & 1

num & 1バリアントは、数値の値表現のビットにアクセスする必要がある状況のために予約する必要があります。このコードを偶数/奇数チェックに使用することは、非常に疑わしい方法です。

score 12 · Accepted Answer

私は「IsEven」関数を定義して使用しているので、それについて考える必要はありません。次に、どちらかの方法を選択し、何かが均一であるかどうかを確認する方法を忘れました。

唯一の注意点は、ビット演算では、2進数での数値の表現について何かを想定しているということですが、モジュロではそうではありません。数値を10進値として解釈しています。これは整数で動作することがほぼ保証されています。ただし、モジュロはdoubleに対して機能しますが、ビット演算は機能しないことを考慮してください。

score 9 · Accepted Answer

最近のコンパイラは両方のオプションに対して同じアセンブリを作成することが何度も言及されています。先日どこかで見たLLVMデモページを思い出したので、やってみようと思いました。これは逸話に過ぎないことを私は知っていますが、それは私たちが期待することを確認します：x%2そしてx&1同じように実装されます。

また、これらの両方をgcc-4.2.1（gcc -S foo.c）でコンパイルしようとしましたが、結果のアセンブリは同じです（そしてこの回答の下部に貼り付けられています）。

最初のプログラム：

int main(int argc, char **argv) {
  return (argc%2==0) ? 0 : 1;
}

結果：

; ModuleID = '/tmp/webcompile/_27244_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

2番目のプログラム：

int main(int argc, char **argv) {
  return ((argc&1)==0) ? 0 : 1;
}

結果：

; ModuleID = '/tmp/webcompile/_27375_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

GCC出力：

.text
.globl _main
_main:
LFB2:
  pushq %rbp
LCFI0:
  movq  %rsp, %rbp
LCFI1:
  movl  %edi, -4(%rbp)
  movq  %rsi, -16(%rbp)
  movl  -4(%rbp), %eax
  andl  $1, %eax
  testl %eax, %eax
  setne %al
  movzbl  %al, %eax
  leave
  ret
LFE2:
  .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support
EH_frame1:
  .set L$set$0,LECIE1-LSCIE1
  .long L$set$0
LSCIE1:
  .long 0x0
  .byte 0x1
  .ascii "zR\0"
  .byte 0x1
  .byte 0x78
  .byte 0x10
  .byte 0x1
  .byte 0x10
  .byte 0xc
  .byte 0x7
  .byte 0x8
  .byte 0x90
  .byte 0x1
  .align 3
LECIE1:
.globl _main.eh
_main.eh:
LSFDE1:
  .set L$set$1,LEFDE1-LASFDE1
  .long L$set$1
ASFDE1:
  .long LASFDE1-EH_frame1
  .quad LFB2-.
  .set L$set$2,LFE2-LFB2
  .quad L$set$2
  .byte 0x0
  .byte 0x4
  .set L$set$3,LCFI0-LFB2
  .long L$set$3
  .byte 0xe
  .byte 0x10
  .byte 0x86
  .byte 0x2
  .byte 0x4
  .set L$set$4,LCFI1-LCFI0
  .long L$set$4
  .byte 0xd
  .byte 0x6
  .align 3
LEFDE1:
  .subsections_via_symbols

score 7 · Accepted Answer

それはすべて文脈に依存します。低レベルのシステムコンテキストの場合、私は実際に＆1アプローチを好みます。これらの種類のコンテキストの多くでは、「偶数」とは、基本的に、2で割り切れるのではなく、下位ビットがゼロであることを意味します。

ただし、ワンライナーにはバグがあります。

あなたが行かなければなりません

if( (x&1) == 0 )

いいえ

if( x&1 == 0 )

後者はxを1==0とANDします。つまり、xを0とANDして、0を生成します。これは、もちろん常にfalseと評価されます。

したがって、あなたが提案したとおりにそれを行った場合、すべての数字は奇妙です！

score 3 · Accepted Answer

最新のコンパイラはモジュロ演算を最適化するため、速度は問題になりません。

モジュロを使用すると理解しやすくなると思いますが、このメソッドをis_even使用する関数を作成するx & 1と、両方の長所が得られます。

score 3 · Accepted Answer

どちらも非常に直感的です。

私は少しエッジを与えるでしょうnum % 2 == 0が、私は本当に好みがありません。確かに、パフォーマンスに関しては、おそらくマイクロ最適化なので、心配する必要はありません。

score 2 · Accepted Answer

私は何年もかけて、ディスク上で消費するスペースに見合う妥当なコンパイラが最適化されると主張しnum % 2 == 0ましたnum & 1 == 0。次に、別の理由で分解を分析し、実際に自分の仮定を検証する機会がありました。

結局、私は間違っていました。Microsoft Visual Studioは、バージョン2013まで、次のオブジェクトコードを生成しますnum % 2 == 0。

    and ecx, -2147483647        ; the parameter was passed in ECX
    jns SHORT $IsEven
    dec ecx
    or  ecx, -2
    inc ecx
$IsEven:
    neg ecx
    sbb ecx, ecx
    lea eax, DWORD PTR [ecx+1]

はい、確かに。これはリリースモードで、すべての最適化が有効になっています。x86またはx64のどちらでビルドしても、実質的に同等の結果が得られます。あなたはおそらく私を信じないでしょう。自分ではほとんど信じられませんでした。

それは本質的にあなたが期待することをしますnum & 1 == 0：

not  eax                        ; the parameter was passed in EAX
and  eax, 1

比較として、GCC（v4.4までさかのぼる）とClang（v3.2までさかのぼる）は、期待どおりの動作を行い、両方のバリアントに対して同一のオブジェクトコードを生成します。ただし、Matt Godboltのインタラクティブコンパイラによると、ICC13.0.1も私の期待に反しています。

確かに、これらのコンパイラは間違っていません。バグではありません。これらの2つのコードスニペットが同一でない理由は（他の回答で適切に指摘されているように）多くの技術的な理由があります。そして、ここで行われるべき「時期尚早の最適化は悪である」という議論が確かにあります。確かに、これに気付くのに何年もかかったのには理由があり、それでも私は誤ってそれに遭遇しただけでした。

しかし、Doug T.が言ったようIsEvenに、ライブラリ内のどこかに関数を定義して、これらの小さな詳細をすべて正しくし、それらについてもう一度考える必要がないようにし、コードを読みやすくするのがおそらく最善です。定期的にMSVCをターゲットにしている場合は、おそらく私が行ったようにこの関数を定義します。

bool IsEven(int value)
{
    const bool result = (num & 1) == 0;
    assert(result == ((num % 2) == 0));
    return result;   
}

score 0 · Accepted Answer

どちらのアプローチも、特にプログラミングに不慣れな人には明らかではありません。inlineわかりやすい名前で関数を定義する必要があります。その中で使用するアプローチは重要ではありません（マイクロ最適化は、プログラムを目立った方法で高速化しない可能性があります）。

とにかく、2）除算を必要としないので、はるかに高速だと思います。

score 0 · Accepted Answer

モジュロによって物事が読みやすくなるとは思いません。どちらも理にかなっており、どちらのバージョンも正しいです。また、コンピューターは数値を2進数で格納するため、2進数バージョンを使用できます。

コンパイラは、モジュロバージョンを効率的なバージョンに置き換えることができます。しかし、それはモジュロを好む言い訳のように聞こえます。

そして、この非常に特殊なケースでの読みやすさは、両方のバージョンで同じです。プログラミングに不慣れな読者は、モジュロ2を使用して数値の偶数を決定できることさえ知らないかもしれません。読者はそれを推測する必要があります。彼はモジュロ演算子さえ知らないかもしれません！

ステートメントの背後にある意味を推測すると、バイナリバージョンを読むのがさらに簡単になる可能性があります。

if( ( num & 1 ) == 0 ) { /* even */ } if( ( 00010111b & 1 ) == 0 ) { /* even */ } if( ( 00010110b & 1 ) == 0 ) { /* odd */ }

（C / C ++ではなく、説明のためにのみ「b」サフィックスを使用しました）

モジュロバージョンでは、操作が詳細でどのように定義されているかを再確認する必要があります（たとえば、ドキュメントをチェックして、それ0 % 2が期待どおりであることを確認してください）。

バイナリANDはより単純で、あいまいさはありません！

二項演算子の落とし穴は、演算子の優先順位のみです。しかし、それはそれらを避ける理由ではないはずです（いつか新しいプログラマーでさえそれらを必要とするでしょう）。

score -2 · Accepted Answer

この時点で、私は単にノイズを追加しているかもしれませんが、読みやすさに関しては、モジュロオプションの方が理にかなっています。コードが読めない場合、それは実質的に役に立たない。

また、これが実際にリソースに縛られているシステムで実行されるコードでない限り（私はマイクロコントローラーを考えています）、コンパイラーのオプティマイザー用に最適化しようとしないでください。

c++ - num％2またはnum＆1を使用して、数値が偶数かどうかを確認しますか？

12 に答える 12

Related

Reference