JavaScriptで2進表現に含まれる1の個数を効率的に計算する方法

問題

JavaScriptで、引数として単一の整数 num を受け取る関数を作成することを考えてみましょう。この関数は、0から num まで（両端を含む）のすべての整数に対応する配列を生成し、各要素にはその数値の2進表現に含まれる「1」の個数を格納します。

例えば、次の入力が与えられた場合：

const num = 4;

期待される出力は以下のとおりです：

const output = [0, 1, 1, 2, 1];

出力の説明

0 の2進表現は「0」（1の個数：0個）、1 は「1」（1個）、2 は「10」（1個）、3 は「11」（2個）、4 は「100」（1個）となるためです。

実装例

const num = 4;

const mapBinary = (num = 0) => {
  if (num === 0) {
    return [0];
  }
  const res = [0];
  for (let i = 1; i <= num; i++) {
    const n = i % 2 === 0 ? res[i / 2] : res[Math.floor(i / 2)] + 1;
    res.push(n);
  }
  return res;
};

console.log(mapBinary(num));

コードの解説

ビット数を計算する際、以下の性質を意識すると処理がぐっとシンプルになります。

• numberOfBits(n) === numberOfBits(2 * n)
  数値を2倍にすると末尾に「0」が1つ追加されるだけで、「1」の個数自体は変わりません。

• n が偶数の場合
  n の最下位ビットは必ず 0 になるため、n ÷ 2 の結果に含まれる1の個数をそのまま利用できます。

• n が奇数の場合
  (n − 1) / 2 の末尾ビットを 1 に置き換えたものと考えることができ、次の式が成り立ちます。
  numberOfBits(n) === numberOfBits(Math.floor(n / 2)) + 1

つまり、各数値の答えはすでに計算済みのより小さい値（i / 2）から導き出せるため、ループを一度回すだけで O(num) の計算量で全体を求められます。これは動的計画法（DP）の考え方を応用した効率的なアプローチです。

別解：ビット演算を使う方法

ビット演算を活用したい場合は、i & (i - 1) というテクニックが便利です。これは数値の最下位にある「1」を消去する操作で、次のように簡潔に書けます。

const mapBinaryBitwise = (num = 0) => {
  const res = new Array(num + 1).fill(0);
  for (let i = 1; i <= num; i++) {
    res[i] = res[i & (i - 1)] + 1;
  }
  return res;
};

なお、toString(2) で2進文字列に変換して「1」を数える方法も直感的ですが、大量の数値を処理する場合は上記のような漸化式ベースの手法の方が高速に動作します。

実行結果

コンソールには次の出力が表示されます。

[ 0, 1, 1, 2, 1 ]