โปรแกรม C หาคู่ตัวเลขที่ให้ค่า AND สูงสุดในอาร์เรย์

โจทย์

กำหนดอาร์เรย์จำนวนเต็มบวก n ตัว หาคู่ตัวเลขที่ให้ผลลัพธ์ Bitwise AND สูงสุด

ตัวอย่าง

Input: {4, 8, 12, 16}
Output: pair = 8 12, Max AND = 8  (8 & 12 = 8)

Input: {4, 8, 16, 2}
Output: No possible AND, Max AND = 0

อัลกอริทึม (Bit Manipulation)

1. ตรวจสอบบิตจาก MSB (bit 31) ลงมาจน LSB (bit 0)
2. สำหรับแต่ละบิต: ลองเซตบิตนั้นใน result แล้วตรวจสอบว่ามีอย่างน้อย 2 ตัวเลขในอาร์เรย์ที่มีบิต pattern นี้ครบหรือไม่
3. ถ้ามี ≥ 2 ตัว → เก็บบิตนั้นไว้ใน result
4. หลังได้ max AND value แล้ว หาคู่ตัวเลข: วนหา 2 ตัวแรกที่ (arr[i] & result) == result

ฟังก์ชัน checkBit

นับจำนวนตัวเลขในอาร์เรย์ที่ (pattern & arr[i]) == pattern

โค้ดภาษา C

#include <stdio.h>

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

int maxAND(int arr[], int n) {
    int res = 0, count;
    for (int bit = 31; bit >= 0; bit--) {
        count = checkBit(res | (1 << bit), arr, n);
        if (count >= 2)
            res |= (1 << bit);
    }
    if (res == 0)
        printf("no possible and\n");
    else {
        printf("Pair with maximum AND= ");
        count = 0;
        for (int i = 0; i < n && count < 2; i++) {
            if ((arr[i] & res) == res) {
                count++;
                printf("%d ", arr[i]);
            }
        }
    }
    return res;
}

int main() {
    int arr[] = {5, 6, 2, 8, 9, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int ma = maxAND(arr, n);
    printf("\nThe maximum AND value= %d", ma);
    return 0;
}

ผลลัพธ์

Pair with maximum AND= 8 9
The maximum AND value= 8

ความซับซ้อน: O(32 × n) = O(n) เร็วมากกว่าการตรวจสอบทุกคู่ O(n²)