คำชี้แจงปัญหา
รับอาร์เรย์ขององค์ประกอบบวก n เราจำเป็นต้องค้นหาค่าบิตสูงสุดและค่าที่สร้างโดยคู่ขององค์ประกอบจากอาร์เรย์
ตัวอย่าง
หากอาร์เรย์อินพุตคือ {10, 12, 15, 18} ค่าสูงสุดของระดับบิต AND คือ 12
อัลกอริทึม
ผลลัพธ์ของการดำเนินการระดับบิต AND ในบิตเดียวจะสูงสุดเมื่อทั้งสองบิตเป็น 1 เมื่อพิจารณาคุณสมบัตินี้ -
- เริ่มจาก MSB และตรวจสอบว่าเรามีองค์ประกอบอย่างน้อยสององค์ประกอบของอาร์เรย์ที่มีการตั้งค่าไว้หรือไม่
- ถ้าใช่ 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
