C++で1つ前の数値の2進表現を求める方法

この記事では、ある数値の2進表現が与えられたときに、そこから1を引いた結果となる「1つ前の数値」の2進表現を求める方法について解説します。

2進表現とは

2進表現（バイナリ表現）とは、数値の基数を2に変換し、0と1のみを使って数値を表す方法です。

例えば、23の2進表現は 10111 となります。

本記事の課題では、数値 n が2進形式で与えられ、n-1 の2進表現を求めることが目標になります。

2進数の減算の基本

この問題を解くためには、2進数の減算の基礎知識が必要です。2進形式で0または1から1を引くとどうなるかを見てみましょう。

• 0 − 1 = 1（次の桁から1を借りる）
• 1 − 1 = 0

具体例

以下の例で問題をより深く理解しましょう。

入力 : 101101100
出力 : 101101011
説明 : (101101100)2 は 364 の2進表現です。
その1つ前の数値は 363 であり、その2進表現は (101101011)2 です。
ここでは2進減算を行い、元の数値の2進表現から (1)2 を引いて結果を得ています。

解法のロジック

このプログラムの背後にあるロジックを確認し、それをもとにアルゴリズムを設計します。

数値の2進表現から1を引くには、右端（最下位ビット）から走査を開始し、最初に「1」が出現するまで、通過したすべての「0」を「1」に反転していきます。「1」に出会ったら、そのビットを「0」に反転して処理を終了し、最終的な結果を返します。

これは通常の10進数で繰り上がり（キャリー）を扱うのと同じ考え方で、2進数では「繰り下がり（ボロー）」が発生する仕組みです。

アルゴリズム

ステップ 1 : 右から左へ、すなわち n-1 から 0 まで走査する。
ステップ 2 : 「1」に遭遇したら、それを「0」に変更してループを抜ける。
ステップ 3 : 「0」に遭遇したら、それを「1」に変更する。
ステップ 4 : 結果の文字列を出力する。

C++での実装例

上記のアルゴリズムを実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
string previousNumber(string num) {
    int n = num.size();
    if (num.compare("1") == 0)
        return "0";
    int i;
    for (i = n - 1; i >= 0; i--) {
        if (num.at(i) == '1') {
            num.at(i) = '0';
            break;
        } else
            num.at(i) = '1';
    }
    if (i == 0)
        return num.substr(1, n - 1);
    return num;
}
int main() {
    string number = "1011011000";
    cout<<"the Binary representation of the number is "<<number<<endl;
    cout<<"Binary representation of previous number is "<<previousNumber(number);
    return 0;
}

出力結果

The Binary representation of the number is 1011011000
Binary representation of previous number is 1011010111

まとめ

このように、2進表現で表された数値から1を引く操作は、右端から「1」を探して反転させるだけで簡単に実装できます。計算量は文字列の長さに比例する O(n) となり、非常に効率的な手法です。特別なケースとして、入力が「1」の場合は「0」を返し、「1000…0」のような場合は先頭の桁が不要になるため削除する処理も忘れずに行いましょう。