ค่า Bitwise AND สูงสุดของคู่ในอาร์เรย์ใน C++

โจทย์

ได้รับอาร์เรย์ n องค์ประกอบบวก ต้องการหาค่า Bitwise AND สูงสุดที่เกิดจากคู่ใดคู่หนึ่งของอาร์เรย์

ตัวอย่าง

ถ้าอินพุตอาร์เรย์คือ {10, 12, 15, 18} ค่า Bitwise AND สูงสุดคือ 12

อัลกอริทึม

ผลลัพธ์ของ Bitwise AND บนบิตเดียวจะสูงสุดเมื่อทั้งสองบิตเป็น 1 พิจารณาคุณสมบัตินี้

• เริ่มจาก MSB ตรวจสอบว่ามีอย่างน้อย 2 องค์ประกอบในอาร์เรย์ที่มีบิตนั้นเป็น 1 หรือไม่
• ถ้ามี บิต MSB นั้นจะเป็นส่วนหนึ่งของคำตอบและบวกเข้าไปในผลลัพธ์ มิฉะนั้นจะทิ้งบิตนั้น
• วนลูปจาก MSB ถึง LSB (32 ถึง 1) สำหรับตำแหน่งบิต สามารถตรวจสอบได้ง่ายว่าบิตไหนเป็นส่วนหนึ่งของคำตอบ และเก็บบิตเหล่านั้นสะสมไว้

ตัวอย่างโค้ด

#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 ((pattern & arr[i]) == pattern) {
            ++cnt;
        }
    }
    return cnt;
}

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

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

ผลลัพธ์

Maximum bitwise AND = 12