C++で1からnまでのK個の数値を使用した最大XOR

この問題では、2つの正の整数nとkが与えられます。私たちのタスクは、最大X数を使用して1からnまでの最大XORを見つけることです

問題を理解するために例を見てみましょう

入力 − n =5、k =2

出力 − 7

説明 −

elements till 5 is 1, 2, 3, 4, 5
Selecting all XOR pairs:
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
The maximum here is 7.

この問題を解決するために、数値のすべてのビットが設定されているときに、数値の任意の組み合わせに対して最大のXORを見つけることができます。

したがって、数値が5の場合、その2進数は101であり、最大XORは111、つまり7になります。

ただし、最大XORに使用される要素の数が1の場合、最大XORは1です。それ以外の場合、最大XORは、すべてのビットを設定することによって検出されます。

例

ソリューションの動作を説明するプログラム

#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<<"The maximum XOR of "<<k<<" numbers from 1 to"<<n<<" is "<<maxXor(n, k);
   return 0;
}

出力

The maximum XOR of 2 numbers from 1 to 5 is 7