Chương trình C++ tìm phần tử lớn nhất mảng không dùng toán tử điều kiện

Cho mảng A, tìm phần tử lớn nhất nhưng không dùng toán tử điều kiện. Ví dụ A=[12,63,32,24,78,56,20] → max=78.

Giải pháp: dùng phép AND bitwise. Thêm INT_MAX (tất cả bit 1) vào mảng. Tìm giá trị AND lớn nhất của mọi cặp. Giá trị max này sẽ là AND của INT_MAX và phần tử lớn nhất gốc, chính là kết quả.

Ví dụ mã nguồn

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

Kết quả đầu ra

Largest element is: 78