Tìm phần tử lớn nhất từ ​​mảng mà không cần sử dụng toán tử điều kiện trong C ++

Giả sử chúng ta có một mảng A với một số phần tử. Chúng ta phải tìm phần tử lớn nhất trong mảng A, nhưng hạn chế là chúng ta không thể sử dụng bất kỳ toán tử điều kiện nào. Vì vậy, nếu A =[12, 63, 32, 24, 78, 56, 20], thì phần tử tối đa sẽ là 78.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phép toán bitwise AND. lúc đầu, chúng ta sẽ chèn thêm một phần tử INT_MAX (trong đó tất cả các bit là 1) trong mảng. Sau đó, chúng tôi sẽ cố gắng tìm giá trị AND lớn nhất của bất kỳ cặp nào từ mảng. Giá trị tối đa thu được này sẽ chứa giá trị AND của INT_MAX và phần tử lớn nhất của mảng ban đầu và đây sẽ là kết quả.

Ví dụ

#include <iostream>
#include <vector>
using namespace std;
int checkBit(int pattern, vector<int> arr, int n) {
   int count = 0;
   for (int i = 0; i < n; i++)
      if ((pattern & arr[i]) == pattern)
         count++;
   return count;
   }
   int findLargestElement(int arr[], int n) {
      vector<int> elements_vector(arr, arr + n);
      elements_vector.push_back(INT_MAX);
      n++;
      int res = 0;
      for (int bit = 31; bit >= 0; bit--) {
         int count = checkBit(res | (1 << bit), elements_vector, n);
         if ((count | 1) != 1)
               res |= (1 << bit);
      }
      return res;
}
int main() {
   int arr[] = {12, 63, 32, 24, 78, 56, 20};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Largest element is: " << findLargestElement(arr, n);
}

Đầu ra

Largest element is: 78