XOR tối đa sử dụng K số từ 1 đến n trong C ++

Trong bài toán này, chúng ta cho hai số nguyên dương n và k. Nhiệm vụ của chúng ta là tìm x hoặc tối đa trong khoảng từ 1 đến n bằng cách sử dụng số X tối đa

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - n =5, k =2

Đầu ra - 7

Giải thích -

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.

Để giải quyết vấn đề này, XOR tối đa có thể được tìm thấy cho bất kỳ tổ hợp số nào được tìm thấy khi tất cả các bit của số được đặt.

Vì vậy, nếu số là 5 nhị phân của nó là 101, thì XOR tối đa sẽ là 111, tức là 7.

Nhưng nếu số phần tử được lấy cho XOR tối đa là 1 thì XOR tối đa là 1. Ngược lại, XOR tối đa sẽ được tìm thấy bằng cách đặt tất cả các bit.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

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