Cặp số cho giá trị AND bitwise lớn nhất trong khoảng [L, R] trong C++

Đề bài

Cho khoảng [L, R], tìm cặp (X, Y) với L ≤ X < Y ≤ R sao cho X & Y (AND bitwise) lớn nhất. In ra giá trị AND lớn nhất đó.

Ví dụ: L=1, R=10. Giá trị max = 8 (từ cặp 8 & 9: 1000 & 1001 = 1000).

Thuật toán

Duyệt mọi cặp (i, j) trong [L, R], tính i & j, giữ giá trị lớn nhất. Độ phức tạp O((R-L)²), chấp nhận được với khoảng nhỏ.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

int getMaxBitwiseAndValue(int L, int R) {
    int maxValue = L & R;
    for (int i = L; i < R; ++i)
        for (int j = i + 1; j <= R; ++j)
            maxValue = max(maxValue, i & j);
    return maxValue;
}

int main() {
    int L = 1, R = 10;
    cout << "Gia tri AND lon nhat = " << getMaxBitwiseAndValue(L, R) << endl;
    return 0;
}

Kết quả

Gia tri AND lon nhat = 8

Lưu ý: Với khoảng lớn, có thể tối ưu bằng quan sát: giá trị AND lớn nhất thường đạt được ở cặp (R-1, R) hoặc các số có tiền tố bit chung dài nhất.