【C++】1からnまでの数値からk個を選んだときの最大XORを求める方法

問題の概要

この問題では、2つの正整数 n と k が与えられます。求めるのは、1からnまでの数値の中からk個の数を選んだ場合に得られるXOR(排他的論理和)の最大値です。

例で理解しよう

入力 − n = 5, k = 2

出力 − 7

説明 −

5以下の要素は 1, 2, 3, 4, 5
すべてのXORの組み合わせ:
1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4
2^3 = 4, 2^4 = 6, 2^5 = 7
3^4 = 7, 3^5 = 6
4^5 = 1
この中で最大の値は 7 です。

解法のアプローチ

この問題を解く鍵となるのは、XORの性質です。2つの数値のXORが最大になるのは、結果のすべてのビットが1(セットされた状態)になるときです。

例えば、n = 5 の2進数表現は 101 なので、最大のXOR値は 111、つまり 7 になります。

ただし、選択する要素数が1の場合(k = 1)、XOR演算は行われないため、最大値は n そのものになります。それ以外の場合は、n より大きい最小の2のべき乗から1を引くことで、すべてのビットがセットされた最大XOR値を求めることができます。

アルゴリズムの流れ

1. k が 1 の場合は、n をそのまま返します。
2. それ以外の場合、result を 1 で初期化し、result が n を超えるまで左シフト(2倍)を繰り返します。
3. 最後に result から 1 を引いた値を返します。これがすべてのビットがセットされた最大XOR値です。

このアルゴリズムの計算量は O(log n) であり、非常に効率的です。

実装例

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

#include <iostream>
using namespace std;
int maxXor(int n, int k) {
    if (k == 1)
        return n;
    int result = 1;
    while (result <= n)
        result <<= 1;
    return result - 1;
}
int main() {
    int n = 5, k = 2;
    cout<<"1から"<<n<<"までの"<<k<<"個の数値の最大XORは "<<maxXor(n, k);
    return 0;
}

出力

1から5までの2個の数値の最大XORは 7

まとめ

最大XORの問題は、ビット演算の性質を理解すれば全探索を行わずに効率的に解くことができます。n より大きい最小の2のべき乗から1を引くというシンプルな手法により、O(log n) の時間で答えを求められます。ビット操作系の問題では、2進数表現での考え方が重要になるため、ぜひ覚えておきましょう。