C++で一方の数値のセットビットに対応して他方の数値のビットを反転する方法

問題概要

本記事では、2つの整数値が与えられたときに、「一方の数値のセットビット（1となっているビット）の位置に対応して、もう一方の数値のビットを反転（トグル）する」という操作を実現するC++プログラムを紹介します。

問題の理解

まず、具体例を使って問題内容を確認しましょう。

入力: 3 7
出力: 4

3の2進数表現: 011
7の2進数表現: 111

数値「3」は2進数で「011」と表されるため、下位から0桁目と1桁目がセットビットです。そこで、もう一方の数値「7」（2進数で「111」）の対応するビット、すなわち0桁目と1桁目を反転します。その結果は「100」となり、10進数では「4」に相当します。

解決アプローチ

この問題は、XOR（排他的論理和）演算を利用することで非常にシンプルに解決できます。XOR演算の性質上、片方のオペランドのビットが「1」である位置では、もう片方の対応するビットが必ず反転されるためです。

XOR演算の真理値表は以下の通りです。

• 0 ^ 0 = 0（変化なし）
• 0 ^ 1 = 1（変化なし）
• 1 ^ 0 = 1（反転）
• 1 ^ 1 = 0（反転）

つまり、数値aのセットビットの位置にある数値bのビットだけが反転され、それ以外のビットは元のまま維持されます。これはまさに本問題で求められている動作であり、答えは単純に「a ^ b」を計算するだけで得られます。

C++での実装例

以下は、この解法の動作を示すサンプルプログラムです。

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

int main(){
    int a = 3, b = 7;
    cout<<"The numbers are "<<a<<" & "<<b<<endl;
    cout<<"The result of flipping bits is "<<(a ^ b);
    return 0;
}

出力

The numbers are 3 & 7
The result of flipping bits is 4

計算量

・時間計算量：O(1) ― 単一のXOR演算のみで処理が完了します。
・空間計算量：O(1) ― 追加のメモリは不要です。

まとめ

「ある数値のセットビットの位置で、別の数値のビットをトグルする」という操作は、XOR演算の基本的な性質を活用すれば1行で実装できます。ビット演算の基礎をしっかり理解しておくことで、この種の問題にも効率的に対処できるようになるでしょう。