C++で2進表現における隣接する2つの1の間の最大0の個数を求める方法

問題概要

整数 n が与えられたとき、その2進表現において隣り合う2つの1の間に存在する0の最大個数を求めるのが課題です。ただし、2進表現に1が2つ未満しか含まれていない場合は -1 を返します。

具体例

入力が 35 の場合、2進表現は次のようになります。

00100011

この2進表現では、隣接する2つの1の間に3つの0が存在します。したがって、答えは 3 となります。

アルゴリズム

この問題はビットシフト演算子を使うことで効率的に解けます。n の2進表現の中から隣接する2つの1の位置を見つけ、その位置の差を最大化することを考えます。

• 数値が 0 または 2 のべき乗である場合（1が1つしかない場合）は -1 を返します。
• 変数 prev を、最下位側で最初に見つかった1の位置で初期化します。これは「直前に見つけた1の位置」を記憶しておくための変数です。
• もう1つの変数 cur を用意し、prev の直後に現れる隣接する1の位置を格納します。
• cur - prev - 1 を計算すると、それが隣接する2つの1の間の0の個数になります。この値をこれまでの最大値と比較し、より大きければ更新します。その後 prev = cur として次の反復に備えます。
• 補助変数 setBit を使用して n の全ビットを順に走査し、現在調べているビットが 0 か 1 かを判定します。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int getMaxZeros(int n) {
    // 0 または 2 のべき乗の場合は -1 を返す
    if (n == 0 || ((n & (n - 1)) == 0)) {
        return -1;
    }
    int setBit = 1;
    int prev = 0;
    int i;

    // 最下位側の最初の1の位置を探す
    for (i = 1; i < sizeof(int) * 8; ++i) {
        ++prev;
        if ((n & setBit) == setBit) {
            setBit = setBit << 1;
            break;
        }
        setBit = setBit << 1;
    }

    int maxZeros = INT_MIN;
    int cur = prev;

    // 隣接する1同士の間の0の個数を調べて最大値を更新
    for (int j = i + 1; j <= sizeof(int) * 8; ++j) {
        ++cur;
        if ((n & setBit) == setBit) {
            if (maxZeros < (cur - prev - 1)) {
                maxZeros = cur - prev - 1;
                prev = cur;
            }
        }
        setBit = setBit << 1;
    }
    return maxZeros;
}

int main() {
    int n = 35;
    cout << "Maximum zeros = " << getMaxZeros(n) << endl;
    return 0;
}

出力結果

Maximum zeros = 3

まとめ

このアルゴリズムでは、n & setBit によるビット判定と setBit << 1 による左シフトを組み合わせることで、数値を1桁ずつ走査しながら隣接する1の位置を追跡しています。計算量は O(log n)、つまりビット長に比例した効率で処理でき、追加のメモリもほとんど不要なシンプルな手法です。