Giá trị XOR lớn nhất sử dụng K số từ 1 đến n trong C++

Trong bài toán này, chúng ta được cho hai số nguyên dương n và k. Nhiệm vụ là tìm giá trị XOR lớn nhất từ 1 đến n sử dụng tối đa K số.

Hãy xem một ví dụ để hiểu bài toán:

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

Đầu ra – 7

Giải thích –

các phần tử đến 5 là 1, 2, 3, 4, 5
Chọn tất cả các cặp 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
Giá trị lớn nhất ở đây là 7.

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

Vì vậy, nếu số là 5, nhị phân là 101, XOR lớn nhất sẽ là 111 tức là 7.

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

Ví dụ

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

#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<<"Giá trị XOR lớn nhất của "<<k<<" số từ 1 đến "<<n<<" là "<<maxXor(n, k);
    return 0;
}

Kết quả

Giá trị XOR lớn nhất của 2 số từ 1 đến 5 là 7