55

数が偶数か奇数かを見つける最も速い方法は何ですか？

4

11 に答える 11

71

ということはよく知られている

static inline int is_odd_A(int x) { return x & 1; }

よりも効率的です

static inline int is_odd_B(int x) { return x % 2; }

しかし、オプティマイザーをオンにするis_odd_Bと、is_odd_A? いいえ — を使用するとgcc-4.2 -O2、次のようになります (ARM アセンブリで):

_is_odd_A:
    and r0, r0, #1
    bx  lr

_is_odd_B:
    mov r3, r0, lsr #31
    add r0, r0, r3
    and r0, r0, #1
    rsb r0, r3, r0
    bx  lr

is_odd_Bよりも 3 命令多くかかることがわかりますis_odd_A。主な理由は

((-1) % 2) == -1
((-1) & 1) ==  1

ただし、次のすべてのバージョンは と同じコードを生成しますis_odd_A。

#include <stdbool.h>
static inline bool is_odd_D(int x) { return x % 2; }      // note the bool
static inline int  is_odd_E(int x) { return x % 2 != 0; } // note the !=

これは何を意味するのでしょうか？通常、オプティマイザーは十分に洗練されているため、これらの単純なものについては、最も明確なコードで十分に最高の効率を保証できます。

于 2010-02-09T15:00:19.313 に答える
7

通常の方法:

int number = ...;
if(number % 2) { odd }
else { even }

別：

int number = ...;
if(number & 1) { odd }
else { even }

GCC 3.3.1 および 4.3.2 でテストされ、どちらもand命令 (x86 でコンパイル) になるため、(コンパイラの最適化なしで) 速度はほぼ同じdivです。まったくテストしないでください。

于 2010-02-09T13:00:16.987 に答える
6 
bool is_odd = number & 1;
于 2010-02-09T12:58:25.740 に答える
5

(x & 1) が true の場合は奇数、それ以外の場合は偶数です。

于 2010-02-09T12:57:43.417 に答える
2 
int is_odd(int n)
{
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else
      return !is_odd(n - 1);
}

ちょっと待って、あなたは最も面白い方法ではなく、最も速い方法だと言いました。私の悪い;）

上記の関数はもちろん正の数に対してのみ機能します。

于 2010-02-09T14:30:08.877 に答える
2

最後のビットが 1 かどうかを確認します。

int is_odd(int num) {
  return num & 1;
}
于 2010-02-09T12:59:17.783 に答える
2 
int i=5;
if ( i%2 == 0 )
{
   // Even
} else {
   // Odd
}
于 2010-02-09T12:57:18.897 に答える
2

整数の場合は、おそらく最下位ビットをチェックするだけです。ゼロでもカウントされます。

于 2010-02-09T12:57:58.530 に答える
2

移植可能な方法は、モジュラス演算子を使用すること%です:

if (x % 2 == 0) // number is even

2 の補数アーキテクチャでのみ実行することがわかっている場合は、ビットごとの and を使用できます。

if (x & 0x01 == 0) // number is even

モジュラス演算子を使用すると、ビットごとの and に比べてコードが遅くなる可能性があります。ただし、次のすべてが当てはまる場合を除き、私はそれを使い続けます。

  1. 厳しいパフォーマンス要件を満たしていません。
  2. 多くのことを実行x % 2しています(たとえば、何千回も実行されているタイトなループで)。
  3. プロファイリングは、mod オペレーターの使用がボトルネックであることを示しています。
  4. プロファイリングは、ビットごとの AND を使用することでボトルネックが解消され、パフォーマンス要件を満たすことができることも示しています。
于 2010-02-09T14:49:25.693 に答える
1

あなたの質問は完全に指定されていません。とにかく、答えはコンパイラとマシンのアーキテクチャに依存します。たとえば、1 の補数または 2 の補数の符号付き数値表現を使用しているマシンを使用していますか?

私は自分のコードを最初に正しく、2 番目に明確に、3 番目に簡潔に、最後に高速になるように記述します。したがって、このルーチンを次のようにコーディングします。

/* returns 0 if odd, 1 if even */
/* can use bool in C99 */
int IsEven(int n) {
    return n % 2 == 0;
}

この方法は正しく、LSB をテストするよりも明確に意図を表現しています。簡潔で、信じられないかもしれませんが、非常に高速です。プロファイリングで、このメソッドがアプリケーションのボトルネックであることがわかった場合にのみ、それから逸脱することを検討します。

于 2010-02-09T14:30:09.107 に答える
0

最下位ビットを確認します。

if (number & 0x01) {
  // It's odd
} else {
  // It's even
}
于 2010-02-09T12:59:43.897 に答える