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