C++で1ビット反転したときに得られる最長の「1」の連続列を求める方法

問題の概要

ある整数 n が与えられたとき、その中の 1ビットだけを反転（フリップ）することで、最も長く連続する「1」の並びを作ることを考えます。

例として、数値が 13 の場合をみてみましょう。13 の2進表現は 1101 です。ここで 0 を 1 に反転すると 1111 となり、4桁すべてが 1 になります。これが反転によって実現できる最長の「1」の連続列です。

解法のアプローチ

この問題は、与えられた数値の各ビットを下位から順に走査することで効率的に解けます。走査中は次の2つのカウンタを管理します。

• curr（現在の長さ）：現在進行中の「1」の連続列の長さ
• prev（直前の長さ）：ひとつ前の「1」の連続列の長さ

ビットが 1 であれば curr を増やし、0 を見つけた時点で prev を更新します。具体的には、次のビットが 1 なら prev を curr に設定し、次のビットも 0 なら prev を 0 に戻します。こうすることで、「0 をひとつ挟んで隣接する2つの 1 の連続列」をつなげた長さ（prev + curr + 反転分の1）を常に追跡できます。

なお、すべてのビットが 1 の場合（~number == 0）は反転の余地がないため、int 型の全ビット数をそのまま返します。

C++での実装例

#include<iostream>
using namespace std;
int singleFlipMaxOnes(unsigned number) {
    if (~number == 0)
        return 8*sizeof(int);
    int curr = 0, prev = 0, max_size = 0;
    while (number != 0) {
        if ((number & 1) == 1)
            curr++;
        else if ((number & 1) == 0) {
            prev = (number & 2) == 0 ? 0 : curr;
            curr = 0;
        }
        max_size = max(prev + curr, max_size);
        number >>= 1;
    }
    return max_size + 1;
}
int main() {
    cout << "Maximum length of the sequence with 1s: " << singleFlipMaxOnes(13);
}

実行結果

Maximum length of the sequence with 1s: 4

まとめ

このアルゴリズムは数値のビット数に比例した計算量 O(log n) で動作し、余分なメモリを必要としません。ビット演算と2つのカウンタだけで解けるシンプルかつ実用的な手法です。入力 13（2進数 1101）に対しては、0 を 1 に反転して 1111 となるため、最大長 4 が出力されます。