C++で条件演算子を使わずに配列の最大要素を求める方法

問題の概要

いくつかの要素を含む配列 A があるとします。この配列 A の中から最大の要素を見つけたいのですが、条件演算子を一切使用してはならないという制約が課されています。例えば、A = [12, 63, 32, 24, 78, 56, 20] という配列が与えられた場合、求める最大要素は 78 です。

解決のアプローチ：ビット演算を活用する

この問題を解くカギとなるのがビット単位のAND演算です。基本的な考え方は次の通りです。

1. まず、すべてのビットが 1 になっている特殊な値 INT_MAX を配列に 1 つ追加します。
2. 続いて、最上位ビット（第31ビット）から最下位ビット（第0ビット）へ向かって、1 ビットずつ答えを組み立てていきます。
3. 各ビット位置では、そのビットを立てたパターンを満たす要素が配列内に何個あるかを数えます。INT_MAX はどんなパターンにも一致するため、元の配列の要素が 1 つでもパターンに合致すれば、合計の一致数は 2 以上になります。
4. この判定には (count | 1) != 1 という式を用います。count が 0 または 1 のときに限り count | 1 は 1 になるため、count が 2 以上（＝元の配列の要素が存在する）の場合にのみ、そのビットを結果に採用できます。

こうして構築された最終的な値は、INT_MAX と元の配列の最大要素とのAND値と一致します。言い換えれば、それこそが求めていた最大要素そのものです。

C++での実装例

#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); // 全ビットが1の値を追加
    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);
}

実行結果

Largest element is: 78

コードのポイント

• checkBit()：指定されたビットパターンを満たす要素の個数を返す補助関数です。
• findLargestElement()：INT_MAX を配列へ追加したうえで、上位ビットから貪欲的に結果を組み立てるメイン関数です。
• 大小比較による直接的な最大値の選択を行わず、ビット演算だけで最大要素を特定できる点がこの手法の大きな特徴です。