C++で次のスパース数を効率的に求める方法

この記事では、整数Nが与えられたときに、Nより大きい最小の「スパース数」を求めるプログラムをC++で作成する方法を解説します。

スパース数とは？

スパース数とは、2進数表現に隣接する1が一切含まれない特殊な数のことです。

例：5（101）、16（10000）

問題の概要

与えられた数Nに対して、Nより大きい数の中で最小のスパース数を見つける必要があります。

入力例

N = 7

出力例

8

解説

8の2進数表現は「1000」であり、これが7より大きい最小のスパース数となります。

解法1：単純なアプローチ（線形探索）

最もシンプルな解決策は、Nより大きい数を順番にチェックし、最初に見つかったスパース数で処理を終了する方法です。

具体的には、Nから順に各数値がスパース数かどうかを判定するループを回し、スパース数が見つかった時点でループを抜けてその値を返します。見つからない場合は次の数へと進みます。

この方法では、最悪の場合O(N)に近い時間計算量が必要になる点に注意してください。

実装例

#include<iostream>
using namespace std;
bool isSpareNumber(int N){
    int currentBit = (N&1);
    int nextBit ;
    while (N!= 0){
        nextBit = currentBit;
        currentBit = (N&1);
        N >>= 1;
        if(nextBit == currentBit && nextBit == 1 && currentBit == 1)
            return false ;
    }
    return true;
}
int findNextSparseNumber(int N) {
    while(1){
        if(isSpareNumber(N))
            return N;
        N++;
    }
    return -1;
}
int main() {
    int N = 564;
    cout<<"The number is "<<N<<endl;
    cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
    return 0;
}

実行結果

The number is 564
The next Sparse Number is 576

解法2：ビット操作による効率的なアプローチ

より効率的な方法は、数値のビットを直接操作することです。数値を2進数に変換し、隣接する1が現れた箇所を修正していきます。

最下位ビット（LSB）から最上位ビット（MSB）へと走査し、連続する1のペアを見つけたら、その両方の1を0に置き換えて、次の上位ビットを1にします。これをMSBに達するまで繰り返し、最後に2進数を10進数に戻したものが答えとなります。この手法ならO(log N)程度の計算量で処理できます。

具体例

N = 52 の場合を考えてみましょう。

52の2進数表現は「110100」です。

LSB側から走査すると、最初に連続する1のペアが現れるのは「110100」の強調部分です。ここで、両方の1を0に置き換え、次の上位ビットに1を加えると、数は「1000000」となり、これは10進数で64に相当します。

実装例

#include<iostream>
using namespace std;
int findNextSparseNumber(int N) {
    int spNum[16];
    int n = 0;
    while (N != 0) {
        spNum[n] = (N&1);
        n++;
        N >>= 1;
    }
    n++;
    int lastCorrectedBit = 0;
    for (int i= 0 ; i< n; i++) {
        if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1){
            spNum[i+1] = 1;
            for (int j=i; j>=lastCorrectedBit; j--)
                spNum[j] = 0;
                lastCorrectedBit = i+1;
        }
    }
    int sparseNumber = 0;
    for (int i =0; i<n-1; i++)
        sparseNumber += spNum[i]*(1<<i);
    return sparseNumber;
}
int main() {
    int N = 564;
    cout<<"The number is "<<N<<endl;
    cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
    return 0;
}

実行結果

The number is 564
The next Sparse Number is 576