Giá trị AND theo bit tối đa của một cặp trong một mảng trong C ++

Tuyên bố vấn đề

Cho một mảng gồm n phần tử dương. chúng ta cần tìm giá trị AND theo chiều bit tối đa được tạo bởi bất kỳ cặp phần tử nào từ mảng.

Ví dụ

Nếu mảng đầu vào là {10, 12, 15, 18} thì giá trị lớn nhất của bitwise AND là 12.

Thuật toán

Kết quả của phép toán theo bitwise AND trên bit đơn là tối đa khi cả hai bit bằng 1. Xét thuộc tính này -

• Bắt đầu từ MSB và kiểm tra xem chúng ta có tối thiểu hai phần tử của mảng có giá trị đặt không
• Nếu có, thì MSB đó sẽ là một phần của giải pháp của chúng tôi và được thêm vào để dẫn đến kết quả, nếu không, chúng tôi sẽ loại bỏ bit đó
• Tương tự, lặp lại từ MSB sang LSB (32 đến 1) cho vị trí bit, chúng tôi có thể dễ dàng kiểm tra xem bit nào sẽ là một phần của giải pháp của chúng tôi và sẽ tiếp tục thêm tất cả các bit đó vào giải pháp của chúng tôi

Ví dụ

Bây giờ chúng ta hãy xem một ví dụ -

#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;
}

Đầu ra

Maximum bitwise AND = 12