XOR演算を使って2進数文字列の2の補数を求める方法【C++実装例】

2の補数とは

2の補数とは、1の補数（各ビットを反転した値）に1を加えたものです。本記事では、XOR演算を活用して2進数文字列の2の補数を求める方法を解説します。XOR演算を利用することで、1の補数を効率よく計算できます。

基本的な考え方

2進数文字列を最下位ビット（LSB）側から走査し、次の手順で処理を行います。

1. 最初の「1」が現れるまで、すべての「0」をそのまま無視して進みます。
2. 見つかった最初の「1」もそのまま維持します。
3. 以降のすべてのビットを、XOR演算によって反転（トグル）します。

この処理により、LSB側から見て最初の「1」より上位のビットのみが反転され、その結果が2の補数と一致します。

アルゴリズム

get2sComp(bin)

begin
    len := 2進数文字列の長さ
    flag := false
    for i := len-1 down to 0, do
        if bin[i] が 0 かつ flag が未設定なら
            後続の処理をスキップして次の反復へ
        else
            if flag が設定済みなら
                bin[i] := bin[i] の反転
            end if
            flag := true
        end if
    done
    if flag が未設定なら
        bin の先頭に 1 を付けて返す
    else
        return bin
    end if
end

C++による実装例

#include <iostream>
using namespace std;
string get2sComplement(string bin) {
    int n = bin.length();
    bool flag = false; // 1が見つかったかどうかを示すフラグ
    for (int i = n - 1; i >= 0; i--) { // 最下位ビットから走査
        if (bin[i] == '0' && !flag) {
            continue;
        } else {
            if (flag)
                bin[i] = (bin[i] - '0') ^ 1 + '0'; // XORでビットを反転し、ASCII文字に変換
            flag = true;
        }
    }
    if (!flag) // 1が存在しない場合は先頭に1を追加
        return "1" + bin;
    else
        return bin;
}
int main() {
    string str;
    cout << "2進数文字列を入力してください: ";
    cin >> str;
    cout << str << " の2の補数は " << get2sComplement(str);
}

実行結果

2進数文字列を入力してください: 10110110
10110110 の2の補数は 01001010

まとめ

XOR演算を使えば、2進数文字列の2の補数を1回の走査（計算量O(n)）で求められます。最下位ビットから最初の「1」までのビットはそのまま保持し、それ以降のビットだけを反転するという、シンプルで直感的なアルゴリズムです。文字列長に比例した効率的な処理が可能なため、実装も容易です。