Giá trị AND bitwise lớn nhất của một cặp trong mảng trong C++

Đề bài

Cho mảng n số nguyên dương. Tìm giá trị lớn nhất của phép AND bitwise giữa hai phần tử bất kỳ trong mảng.

Ví dụ: {10, 12, 15, 18} → max AND = 12 (12 & 15 = 12).

Thuật toán (Duyệt bit từ MSB đến LSB)

1. Kết quả AND lớn nhất khi các bit đều là 1. Duyệt từ bit cao nhất (31) xuống 0.
2. Với mỗi bit, kiểm tra xem có ít nhất 2 phần tử có bit đó = 1 (kết hợp với các bit đã chọn trước).
3. Nếu có, thiết lập bit đó vào kết quả.

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

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

int checkBits(int* arr, int n, int pattern) {
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        if ((arr[i] & pattern) == pattern) ++cnt;
    return cnt;
}

int getMaxBitwiseAnd(int* arr, int n) {
    int result = 0;
    for (int i = 31; i >= 0; --i) {
        int cnt = checkBits(arr, n, result | (1 << i));
        if (cnt >= 2) result |= (1 << i);
    }
    return result;
}

int main() {
    int arr[] = {10, 12, 15, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max bitwise AND = " << getMaxBitwiseAnd(arr, n) << endl;
    return 0;
}

Kết quả

Max bitwise AND = 12