C++で指定した数値とのXORが最大になる数を求める方法

このチュートリアルでは、指定した数値とのXOR（排他的論理和）演算の結果が最大になる数を求めるプログラムをC++で作成します。

ここでは、扱う数値は8ビットであると仮定します。

XOR演算の基本

XOR演算では、異なるビット同士を演算すると「1」になり、同じビット同士を演算すると「0」になります。この性質を利用すると、ある数値XとのXORが最大になるのは、Xの各ビットをすべて反転させた値、つまり1の補数であることがわかります。

8ビットの場合、すべてのビットが1の値は (1 << 8) - 1、すなわち255です。この値とXのXORを取ることで、Xの各ビットが反転され、XORが最大になる数が得られます。

コード例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int findNumberWithMaximumXOR(int X) {
    return ((1 << 8) - 1) ^ X;
}

int main() {
    int X = 4;
    cout << findNumberWithMaximumXOR(X) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

251

入力が4（2進数で00000100）の場合、各ビットを反転すると11111011、つまり251になります。4と251のXORは255となり、これは8ビットで表現できる最大値です。

まとめ

このように、指定した数値とのXORが最大になる数は、その数の1の補数を求めるだけで簡単に計算できます。ビット演算の基本的な性質を理解していれば、非常にシンプルな実装で済むのがポイントです。

このチュートリアルについて質問がある場合は、コメント欄でお知らせください。