C++でXORを最大化するために削除すべき要素の最小数を求める

問題概要

数値 N が与えられます。1 から N までの要素の中からいくつかを取り除き、残った要素全体の XOR（排他的論理和）が最大になるようにします。このとき、取り除く必要がある要素の最小数を求めるのが課題です。

アルゴリズム

この問題は、次の手順で効率よく解くことができます。

1. n が 1 または 2 の場合は要素を削除する必要がないため、答えは 0
2. n 以上で最小の 2 のべき乗を求め、これを nextNumber とする
   2.1. n == nextNumber または n == (nextNumber - 1) の場合、答えは 1
   2.2. n == (nextNumber - 2) の場合、答えは 0
3. 上記以外の場合、n が偶数なら答えは 1、奇数なら答えは 2

考え方のポイント

1 から n までの連続する整数の XOR 値は、n を 4 で割った余りに応じて決まる規則的なパターンを持つことが知られています。さらに、n を超えない範囲で到達可能な XOR の最大値は「すべてのビットが 1 となっている値（nextNumber - 1）」です。

• n がちょうど 2 のべき乗、またはその値より 1 小さい場合：XOR を最大にするには要素を 1 つだけ削除すればよい
• n が 2 のべき乗より 2 小さい場合：すでに XOR が最大値（nextNumber - 1）に達しているため、削除は不要
• それ以外の偶数の場合：適切な要素を 1 つ削除するだけで最大値にできる
• それ以外の奇数の場合：2 つの要素を削除する必要がある

なお、補助関数 nextPowerOf2 は、ビット演算 n & (n - 1) を使って n が 2 のべき乗かどうかを判定し、そうでなければビット数を数えて次の 2 のべき乗を計算しています。

C++による実装例

#include <iostream>
using namespace std;

int nextPowerOf2(int n){
    if (n && !(n & (n - 1))) {
        return n;
    }
    int cnt = 0;
    while (n) {
        n = n / 2;
        ++cnt;
    }
    return (1 << cnt);
}

int elementsToBeRemoved(int n){
    if (n == 1 || n == 2) {
        return 0;
    }
    int nextNumber = nextPowerOf2(n);
    if (n == nextNumber || n == nextNumber - 1) {
        return 1;
    } else if (n == nextNumber - 2) {
        return 0;
    } else if (n & 1) {
        return 2;
    } else {
        return 1;
    }
}

int main(){
    int n = 10;
    cout << "Numbers to be removed = " << elementsToBeRemoved(n) << endl;
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Numbers to be removed = 1

この例では n = 10 であるため、答えは 1 となります。実際に、要素 4 を 1 つだけ削除すると、残りの要素の XOR は最大値である 15（2進数で 1111）に到達できます。