C++で次の数値の2進表現を求めるアルゴリズムと実装方法

はじめに

この問題では、ある数値の2進表現が与えられ、その次の数値、すなわち与えられた数値に1を加えた結果の数値の2進表現を求めることが求められます。

2進表現とは、数値の基数を2に変換し、0と1のみを用いて数値を表現することです。例えば、14の2進表現は「1110」です。

ここでは、2進形式で表された数値nが与えられ、n+1の2進表現を求める必要があります。

この問題を解くためには、2進数の加算の基礎を理解しておく必要があります。2進形式で0や1に1を加えるとどうなるかを見てみましょう。

0 + 1 = 1
1 + 1 = 10

具体例

実際の例で問題の解き方を確認してみましょう。

入力：010010111
出力：010011000
解説：(010010111)₂ は10進数の152の2進表現であり、その次の数値は153です。153の2進表現は (010011000)₂ となります。ここでは2進加算を用いて、数値の2進表現に2進数の1を加算します。

この例から、数値に2進数の1を加えると、右端から連続する「1」がすべて「0」に変化し、最初に現れた「0」が「1」に反転するという規則性が見て取れます。それでは、このロジックに基づいてアルゴリズムを作成しましょう。

アルゴリズム

ステップ1：右から左へ、つまり添字 n-1 から 0 に向かって走査する
ステップ2：「0」に遭遇したら、それを「1」に変更して処理を終了する
ステップ3：「1」に遭遇したら、それを「0」に変更する
ステップ4：「0」が一度も現れなかった場合は、文字列の先頭に「1」を追加する
ステップ5：結果の文字列を出力する

実装例（C++）

それでは、このアルゴリズムをC++で実装してみましょう。

#include <bits/stdc++.h>
using namespace std;
string nextBinary(string num) {
    int l = num.size();
    int flag = 0;
    for (int i = l - 1; i >= 0; i--) {
        if (num.at(i) == '0') {
            num.at(i) = '1';
            flag = 1;
            break;
        } else
            num.at(i) = '0';
    }
    if (flag == 0)
        num = "1" + num;
    return num;
}
int main() {
    string number = "0111010111";
    cout << "入力された数値の2進表現：" << number << endl;
    cout << "次の数値の2進表現：" << nextBinary(number);
    return 0;
}

出力

入力された数値の2進表現：0111010111
次の数値の2進表現：0111011000

コードの解説

このプログラムでは、文字列として与えられた2進数を右端の桁から順に走査します。「0」が見つかればそれを「1」に変更してループを抜け、「1」であれば「0」に繰り下げながら左へ進みます。すべての桁が「1」だった場合（例：「111」→「1000」）は、繰り上がりが最後まで続くため、文字列の先頭に「1」を追加します。

なお、繰り上がりの判定には変数flagを使用しています。元のコードでは条件が「flag < 0」となっていましたが、flagは0または1の値しか取らないため、この条件は常に偽となり、すべての桁が「1」の場合に正しく動作しません。正しく動作させるには「flag == 0」と判定する必要があるため、上記のコードでは修正しています。

計算量

2進数の桁数をnとすると、最悪の場合すべての桁を走査するため、時間計算量はO(n)となります。空間計算量も、繰り上がりによって先頭に1桁追加される可能性があるためO(n)です。

まとめ

このように、2進数で表された数値に1を加える処理は、右端から「0」を探して「1」に反転させるというシンプルな操作で実現できます。2進加算の仕組みを理解すれば、ビット操作や文字列処理の良い練習問題として活用できるでしょう。