C ++中数组中一对的最大按位AND值
问题陈述
给定n个正元素的数组。我们需要找到数组中任何一对元素生成的最大按位与值。
示例
如果输入数组是{10，12，15，18}，则按位AND的最大值是12。
算法
当两个位均为1时，对单个位进行按位AND运算的结果最大。考虑到此属性-
从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