101

このような関数が必要です：

// return true if 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  
// is_power_of_2(3) => false
bool is_power_of_2(int n);

誰かが私がこれを書くことができる方法を提案できますか？

4

16 に答える 16

209

(n & (n - 1)) == 0最高です。ただし、n = 0の場合は誤ってtrueを返すことに注意してください。そのため、可能であれば、明示的にチェックする必要があります。

http://www.graphics.stanford.edu/~seander/bithacks.htmlには、これを含む巧妙なビットをいじるアルゴリズムの大規模なコレクションがあります。

于 2008-09-20T14:45:50.410 に答える
83

2の累乗には、1ビットのみが設定されます（符号なし数値の場合）。何かのようなもの

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

正常に動作します。2の累乗より1小さい値は、下位ビットのすべて1であるため、ビット単位でANDをとる必要があります。

符号なしの数値を想定していたので、== 0テスト（最初は忘れていましたが、申し訳ありません）で十分です。符号付き整数を使用している場合は、>0のテストが必要になる場合があります。

于 2008-09-20T14:37:15.063 に答える
52

2進数の2の累乗は、次のようになります。

1: 0001
2: 0010
4: 0100
8: 1000

常に正確に1ビットが設定されていることに注意してください。唯一の例外は、符号付き整数の場合です。たとえば、値が-128の8ビット符号付き整数は次のようになります。

10000000

したがって、数値がゼロより大きいことを確認した後、巧妙なビットハックを使用して、1ビットのみが設定されていることをテストできます。

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x−1));
}

より多くのビットのいじりについては、ここを参照してください。

于 2008-09-20T14:40:00.223 に答える
16

アプローチ #1:

数値をひっそりと2で割って確認します。

時間計算量: O(log2n)。

アプローチ #2:

直前の数値とのビット単位の AND は、ゼロに等しい必要があります。

例:数値 = 8 8 の 2 進数: 1 0 0 0 7 の 2 進数: 0 1 1 1 で、両方の数値のビットごとの AND は 0 0 0 0 = 0 です。

時間計算量: O(1)。

アプローチ #3:

ビット単位の XOR は、直前の数値との数値の合計である必要があります。

例:数値 = 8 8 のバイナリ: 1 0 0 0 7 のバイナリ: 0 1 1 1 で、両方の数値のビット単位の XOR は 1 1 1 1 = 15 です。

時間計算量: O(1)。

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

于 2016-01-20T01:58:28.393 に答える
8 
bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}
于 2008-09-20T14:39:28.350 に答える
2

以下は、ブール値の短絡と比較が遅いという事実により、最も支持された回答よりも高速になります。

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x – 1));
}

x が 0 にならないことがわかっている場合

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x – 1));
}
于 2015-10-12T14:43:14.057 に答える
1

これは最速または最短の方法ではありませんが、非常に読みやすいと思います。だから私はこのようなことをします：

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

バイナリは2の累乗に基づいているため、これは機能します。ビットが1つだけ設定されている数値は、2の累乗でなければなりません。

于 2008-09-20T14:40:33.763 に答える
1

C++ で数値が 2 のべき乗であるかどうかをテストする最も簡単な方法は何ですか?

Bit Manipulation Instructionsを備えた最新の Intel プロセッサを使用している場合は、次の操作を実行できます。他の人がすでに回答しているため、ストレートな C/C++ コードは省略していますが、BMI が利用できないか有効になっていない場合は必要です。

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

GCC、ICC、および Clang 信号の BMI サポート__BMI__。AVX2 が使用可能で有効になっている場合、Visual Studio 2015 以降の Microsoft コンパイラで使用できます。必要なヘッダーについては、SIMD 組み込み関数のヘッダー ファイルを参照してください。

私は通常、i686 でコンパイルする場合に_blsr_u64備えて をガードします。_LP64_Clang は、わずかに異なる組み込みシンボル nam を使用するため、少し回避策が必要です。

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

この種のアルゴリズムを見つけることができる良い Web サイトを教えてもらえますか?

この Web サイトはよく引用されます: Bit Twiddling Hacks .

于 2016-09-20T19:36:04.653 に答える
-1

C++で可能です

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}
于 2015-09-14T12:47:16.370 に答える
-2

もう 1 つの方法 (最速ではないかもしれません) は、ln(x) / ln(2) が整数かどうかを判断することです。

于 2008-09-20T15:03:04.037 に答える
-4

これは、T-SQL（SQL Server）のビットシフト方式です。

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

対数を4回実行するよりもはるかに高速です（最初のセットは小数の結果を取得し、2番目のセットは整数のセットと比較を取得します）

于 2013-02-02T01:34:14.510 に答える