समस्या कथन
n सकारात्मक तत्वों की एक सरणी को देखते हुए। हमें सरणी से किसी भी तत्व के जोड़े द्वारा उत्पन्न अधिकतम बिटवाइज़ और मान खोजने की आवश्यकता है।
उदाहरण
यदि इनपुट ऐरे {10, 12, 15, 18} है तो बिटवाइज़ का अधिकतम मान और 12 है।
एल्गोरिदम
बिटवाइज़ और सिंगल बिट पर संचालन का परिणाम अधिकतम होता है जब दोनों बिट 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