C++の配列内のペアの最大ビット単位AND値

問題の説明

n個の正の要素の配列が与えられます。配列から要素の任意のペアによって生成された最大ビット単位のAND値を見つける必要があります。

例

入力配列が{10、12、15、18}の場合、ビット単位のANDの最大値は12です。

アルゴリズム

単一ビットに対するビット単位のAND演算の結果は、両方のビットが1のときに最大になります。このプロパティを考慮すると-

• MSBから開始して、設定値を持つ配列の要素が2つ以上あるかどうかを確認します
• はいの場合、その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