JavaScriptで2進数の「1」同士の最長距離(バイナリギャップ)を求める方法

問題の概要

正の整数 n を受け取る JavaScript 関数を作成しましょう。この関数は、n を2進数で表したときに出現する「1」のうち、隣接する2つの1の間の最長距離(バイナリギャップ)を求めて返します。

もし隣接する1が2つも存在しない場合は、0 を返します。

「隣接」と「距離」の定義

2つの1が隣接しているとは、その間が0のみで区切られている(あるいは何も挟まれていない)状態を意味します。間に別の1が存在する場合、それらは隣接とはみなされません。

また、2つの1の距離は、それぞれのビット位置の差の絶対値として定義されます。たとえば「1001」に含まれる2つの1の距離は 3 です。

具体例

入力が 22 のとき、出力は 2 になります。その理由は以下の通りです。

• 22 の2進数表現は「10110」である
• 最初の隣接ペア(左端の1とその次の1)の距離は 2
• 2番目の隣接ペア(残りの1同士)の距離は 1
• 答えはこれらのうち大きい方、つまり 2

なお、間にもう1つの1を挟んでいるような2つの1は、隣接ペアとしてカウントできない点に注意してください。

実装例

const num = 22;

const binaryGap = (num = 1) => {
   let last = -1; // 直前に見つけた「1」のビット位置(未発見なら -1)
   let ans = 0;   // 最大距離の答え

   // 下位ビットから上位ビットへ向かって全ビットを走査
   for (let i = 0; i < 32; i++) {
      // 現在のビットが「1」かどうかを判定
      if (((num >> i) & 1) === 1) {
         // 前回の「1」がすでに見つかっていれば距離を計算し、最大値を更新
         if (last >= 0) {
            ans = Math.max(ans, i - last);
         }
         last = i;
      }
   }
   return ans;
};

console.log(binaryGap(num));

出力結果

コンソールには次のように表示されます。

2

コードの解説

このアルゴリズムのポイントは、変数 last を使って「直前に見つけた1のビット位置」を記録しておくことです。初期値は -1 であり、「まだ1が一度も見つかっていない」状態を表します。

ループ内では (num >> i) & 1 というビット演算によって、i 番目のビットが1かどうかを判定します。1が見つかった時点で、すでに前回の1が存在していれば(last >= 0)、現在位置との差 i - last を計算し、Math.max() で最大距離を更新します。その後 last を現在の位置に更新して、走査を続けます。

時間計算量は O(log n)、空間計算量は O(1) と非常に効率的で、余分な配列や文字列変換も不要です。ビット演算を活用することで、2進数への変換を行わずとも簡潔に問題を解けるのが魅力です。