C++의 배열에서 쌍의 최대 비트 AND 값

문제 설명

n개의 양수 요소의 배열이 제공됩니다. 배열에서 요소 쌍에 의해 생성된 최대 비트 AND 값을 찾아야 합니다.

예

입력 배열이 {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