【C++】ビット単位ORが最大値以下になるペアの個数を数える方法

整数型の配列が与えられ、その要素から作成できるすべてのペアのうち、ペア同士のビット単位OR（論理和）を計算した結果が、そのペア内の最大値以下となる組み合わせの総数を求めるのが本記事のテーマです。

OR演算の真理値表

まず、OR演算の基本的な挙動を整理しておきましょう。

OR演算では、どちらか一方のビットでも1であれば結果は1になります。この性質により、2つの異なる正整数のORは通常、両方の値以上になります。したがって「ORの結果が最大値以下」となるのは、片方の数値のセットビットがもう片方に完全に含まれている場合だけです。

入力と出力の例

入力: int arr[] = {4, 8, 9, 10, 23}

出力: ビット単位ORが最大値以下となるペアの数 → 3

説明: 配列から作成できる全ペアを検証すると、次のようになります。

条件を満たすペアは (4, 23)、(8, 9)、(8, 10) の3組です。例えば 8 は2進数で 1000、9 は 1001 であり、8 のビットはすべて 9 に含まれるため、8 | 9 = 9 となり条件を満たします。

プログラムで使用するアプローチ

• ペアを作成するために、整数要素の配列を入力として受け取る。
• 配列のサイズを計算し、そのデータを処理用の関数に渡す。
• ペア内の最大値以下となるOR演算の結果を持つペアの数を格納する一時変数 count を用意する。
• 外側のループで i を 0 から配列サイズ - 1 まで回す。
• 内側のループで j を i + 1 から配列サイズまで回す。
• ループ内で arr[i] | arr[j] <= max(arr[i], arr[j]) を判定し、真であれば count を 1 増やす。
• 最後に count を返し、結果を出力する。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// ビット単位ORが最大値以下となるペアをカウントする関数
int Pair_OR(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size - 1; i++){
        for (int j = i + 1; j < size; j++){
            if ((arr[i] | arr[j]) <= max(arr[i], arr[j])){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 4, 8, 9, 10, 23};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of pairs with bitwise OR less than Max are: " << Pair_OR(arr, size);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count of pairs with bitwise OR less than Max are: 3

計算量について

すべてのペアを二重ループで調べるため、時間計算量は O(n²) です。追加で必要なメモリはカウンター程度のみなので、空間計算量は O(1) となります。配列のサイズが大きくなる場合は、各値をビットマスクとして扱い、部分マスクの関係を効率的に数える手法（高次元累積和など）を検討すると、さらに高速化が可能です。