SPOJ.COM - Thuật toán bài MAXXOR - Find the max XOR value

Đề bài:

Bạn được đưa cho 2 số nguyên L và R. Và bạn phải tìm ra giá trị XOR lớn nhất của hai số a và b thỏa mãn L <= a <= R và L <= b <= R.

Đầu vào

Gồm 1 dòng chứa 2 số nguyên L và R thỏa mãn L, R <= 1e9

Đầu ra

In ra một số nguyên duy nhất là kết quả.

Ví dụ

Đầu vào:

1 10 

Đầu ra:

15 

Bạn có thể tham khảo đề bài tiếng anh và submit code tại đây: http://www.spoj.com/problems/MAXXOR/

Phân tích

Bài toán này nếu sử dụng thuật toán vét cạn - brute force thì rõ ràng với L, R tối đa là 10e9 thì chắc chắn sẽ bị time limit. Vì vậy mình sẽ sử dụng thuật toán tham lam - greedy để giải quyết bài toán.

Đối với phép tính XOR thì ta có kết quả như sau:

0 XOR 0 = 0 
0 XOR 1 = 1 
1 XOR 0 = 1 
1 XOR 1 = 0 

Ở đây mình xét toán tử XOR là toán tử với bit. Do đó, mình chỉ quan tâm đến số biểu diễn dạng nhị phân.

Mình sẽ tìm ra vị trí bit mà tại vị trí đó một số có bit biểu diễn là 1 và 1 số có bit biểu diễn là 0. Thì chắc chắn mình sẽ tìm được 2 số a và b mà khi a XOR b sẽ cho kết quả lớn nhất.

Để dễ hiểu, mời bạn xem lại ví dụ trên. Với ví dụ trên đầu vào L = 1 và R = 10. Số L được biểu diễn dạng nhị phân là 0001 và số R được biểu diễn dạng nhị phân là 1010. Mình tìm được vị trí thứ 3 (đánh dấu vị trí từ 0) thỏa mãn. Khi đó mình tìm được 2 số a và b thỏa mãn sẽ là 0b1111 và 0b0000. Và kết quả XOR lớn nhất sẽ là 0b1111 tức là số 15 trong hệ thập phân.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

int main()
{
    // Comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    // Nhập đầu vào
    int L,R;
    cin >> L >> R;

    // Một số nguyên thì tối đa là 32 bít
    // được đánh dấu từ vị trí 0 đến vị trí 31
    // Do đó khởi tạo pos = 31, tức là trỏ đến vị trí bit cao nhất
    int pos = 31;
    while(true)
    {
        // Kiểm tra tại vị trí đó
        // Và dịch dần cho đến khi tìm được vị trí thỏa mãn
        // 1 số được biểu diễn bởi bit 1 và số còn lại được
        // biểu diễn bởi bit 0
        bool check_right = R & (1 << pos);
        bool check_left  = L & (1 << pos);

        // Nếu tìm được thì break khỏi vòng lặp
        // Ngược lại, thì dịch
        if(check_right && !check_left) break;
        else pos--;
    }

    // Kết quả tìm được sẽ là số dạng nhị phân: 0b1111....111
    int result = 0;
    for(int i = 0; i <= pos; i++)
        result = result * 2 + 1;

    cout << result << endl;

    return 0;
}