JavaScriptのビット演算で2の累乗かどうかを判定する方法

はじめに

本記事では、数値を受け取り、それが2の累乗であるかどうかを判定するJavaScript関数の作成方法を解説します。

期待する動作は以下のとおりです。

f(23)   → false
f(16)   → true
f(1)    → true
f(1024) → true

アプローチ：2進数の性質を利用する

2の累乗を2進数で表すと、必ず立っているビット（1）が1つだけになるという特徴があります。

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

この性質を利用すると、以下のビット演算のテクニックで判定が可能です。

num & (num - 1)

この式は、numと「numから1を引いた値」の論理積（AND）を計算します。numが2の累乗の場合、最上位の1つのビットだけが立ち、その下の桁はすべて0です。そこから1を引くと、立っていたビットが0になり、それより下の桁がすべて1に変わります。つまり、両者には共通して立っているビットが存在しないため、演算結果は必ず0になります。

一方、2の累乗以外の数値では、少なくとも共通するビットが残るため、結果は0以外になります。

なお、負の数や0を除外するため、事前に「数値が1以上であること」のチェックも行います。

実装例

以下が実際のコードです。

const num1 = 256;
const num2 = 1024;

const isPowerOfTwo = (num = 1) => {
    if (num < 1) {
        return false;
    };
    return (num & (num - 1)) === 0;
};

console.log(isPowerOfTwo(num1));
console.log(isPowerOfTwo(num2));
console.log(isPowerOfTwo(1));
console.log(isPowerOfTwo(23));

実行結果

コンソールへの出力は次のようになります。

true
true
true
false

まとめ

num & (num - 1) の結果が0になるかどうかを確認することで、ループや再帰を使わずに、O(1)の定数時間で2の累乗かどうかを判定できます。ビット演算ならではのシンプルかつ高速な手法なので、ぜひ活用してみてください。