2の累乗かチェックする方法

2の累乗チェック

正の整数がバイナリ表現でちょうど1つのビットが設定されている場合のみ、2の累乗です。古典的なワンライナーテスト：

function isPowerOf2(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

なぜ動作するか

2の累乗のバイナリは、1つの1の後にゼロが続く形：

  1   = 00000001
  2   = 00000010
  4   = 00000100
  8   = 00001000
 16   = 00010000

1を引くと最下位の設定ビットとそれ以下のすべてのビットが反転：

  8     = 00001000
  8 - 1 = 00000111

ANDすると、重複がないため2の累乗では常にゼロ：

  00001000
& 00000111
──────────
  00000000

2の累乗でない場合、少なくとも1つの上位ビットが残る：

  6     = 00000110
  6 - 1 = 00000101
  6 & 5 = 00000100  (ゼロではない！)

エッジケース

• n = 0: falseを返す。0は2の累乗ではなく、n > 0チェックで処理。
• n < 0: falseを返す。負の数は2の累乗ではない。
• n = 1: trueを返す。2^0 = 1。

関連トリック：次の2の累乗

次の2の累乗に切り上げる：

function nextPowerOf2(n) {
  n--;
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;
  return n + 1;
}

最上位の設定ビットを下方に伝播させ、すべての下位ビットを1で埋め、1を足します。