C++でn XOR (n+1) = kを満たす最小のnを求める方法

問題の概要

正の整数 k が与えられたとき、n XOR (n+1) の計算結果が k と等しくなるような正の整数 n を求めることを考えます。例えば、k = 7(2進数で 111)の場合、答えは 3 になります。3 は 2進数で 011、3 + 1 = 4 は 100 と表され、011 XOR 100 = 111(10進数で 7)となるためです。

アルゴリズムの考え方

この問題は、n の偶奇によって2つの場合に分けて考えることができます。

n が偶数の場合

n が偶数であれば、n の最下位ビットは 0、n + 1 の最下位ビットは 1 となり、それ以外の上位ビットはすべて同一です。したがって、XOR の結果は 1 になります。

n が奇数の場合

n が奇数の場合、n の最下位ビットは 1、n + 1 の最下位ビットは 0 です。このとき、繰り上がり(キャリー)の影響で複数のビットが変化します。キャリーは、左方向へ最初の 0 のビットが現れる位置まで伝播し続けます。その結果、n XOR (n+1) の値は 2^i − 1 になります。ここで i は、n を左から見たときに最初に 0 が現れるビットの位置です。

以上のことから、k が 2^i − 1 の形(2進表現ですべてのビットが 1 の数)で表せる場合、答えは k / 2 となります。それ以外の k に対しては、条件を満たす n は存在しません。

C++での実装例

#include<iostream>
using namespace std;
int findNValue(int k) {
    if (k == 1)
        return 2;
    if (((k + 1) & k) == 0)
        return k / 2;
    return -1;
}
int main() {
    int k = 15;
    cout << "nの値は: " << findNValue(k);
}

実行結果

nの値は: 7

コードの解説

findNValue 関数では、まず k が 1 の場合に 2 を返します。k = 1 のとき k / 2 は 0 となり正の整数にならないため、特別な処理が必要です。実際、n = 2 のとき 2 XOR 3 = 1 となり、条件を満たします。

次に、(k + 1) & k が 0 かどうかを判定しています。これは、k が「2の累乗から 1 を引いた値」(1, 3, 7, 15, 31 …など、2進表現ですべてのビットが 1 の数)であるかを確認する定番のビット演算テクニックです。条件を満たせば k / 2 を返し、満たさなければ -1 を返して解が存在しないことを示します。

k = 15 の場合、15 は 2進数で 1111 すなわち 2^4 − 1 に該当するため、15 / 2 = 7 が出力されます。実際に、7(0111)と 8(1000)の XOR は 1111(15)となり、条件を満たしていることが確認できます。