C++で数値の2進表現に含まれる長さn以上の連続する「1」を検索する方法

問題の概要

2つの整数 x と n が与えられたとき、32ビットの2進表現の中から「長さが n 以上となる最初の連続した1の並び」を探し、その開始位置を返すことを考えます。該当する並びが存在しない場合は -1 を返します。

例えば、x = 35、n = 2 の場合、結果は 31 になります。32ビット整数としての 35 の2進表現は以下のとおりです。

00000000000000000000000000100011

この中で2つの「1」が連続して現れているのはインデックス31の位置なので、答えは 31 となります。

解決のアプローチ

この問題を解くポイントは、「先頭の0（リーディングゼロ）の個数」を求めることです。先頭の0の数をもとに、連続する「1」の並びを順番に特定していきます。処理の流れは以下のとおりです。

1. x の先頭にある0の個数を数え、その分だけ左シフトすることで、最初の「1」を最上位ビットの位置まで移動させます。
2. 次に、ビットを反転した値（~x）の先頭にある0の個数を調べます。この値は、直前に見つかった連続する「1」の長さに対応します。
3. その長さが n 以上であれば現在位置を結果として返します。条件を満たさない場合はさらに左シフトを行い、x が0になるまで同様の処理を繰り返します。

C++による実装例

#include<iostream>
using namespace std;
int leadingZeroCount(int x) {
    unsigned y;
    int n;
    n = 32;
    for(int i = 16; i > 1; i = i/2 ){
        y = x >> i;
        if(y != 0){
            n -= i;
            x = y;
        }
    }
    y = x >> 1;
    if (y != 0)
        return n - 2;
    return n - x;
}
int consecutiveOnePosition(unsigned x, int n) {
    int k, p;
    p = 0;
    while (x != 0) {
        k = leadingZeroCount(x);
        x = x << k;
        p = p + k;
        k = leadingZeroCount(~x);
        if (k >= n)
            return p + 1;
        x = x << k;
        p = p + k;
    }
    return -1;
}
int main() {
    int x = 35;
    int n = 2;
    cout << "Consecutive 1s of length " << n << " is starting from index: " << consecutiveOnePosition(x, n);
}

実行結果

Consecutive 1s of length 2 is starting from index: 31

この実行結果から、x = 35 の場合、長さ2以上の連続する「1」はインデックス31から始まっていることが確認できます。リーディングゼロのカウントとビットシフトを組み合わせることで、効率よく連続する「1」の並びを検索できるのがこのアルゴリズムの特徴です。