C++에서 1에서 n까지의 K 숫자를 사용하는 최대 XOR

이 문제에서는 두 개의 양의 정수 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이면 이진수는 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