C++でビット単位ORが奇数となるペアの個数を求める方法

配列が与えられたとき、ビット単位OR（Bitwise OR）の結果が奇数になるペアの個数を求める問題を解説します。まずは具体例を見てみましょう。

入力：

arr = [1, 2]

出力：

1

この配列では、ビット単位ORが奇数になるペアは1つだけで、そのペアは (1, 2) です。実際に「1 | 2」を計算すると 3 となり、奇数であることが確認できます。

ポイント：ORが奇数になる条件

ビット単位ORの結果が奇数になるのは、「少なくとも一方の値が奇数である場合」です。これは、奇数の最下位ビット（LSB）が 1 であり、OR演算ではどちらか一方でも 1 なら結果も 1 になるためです。この性質を理解しておくと、後述する効率的な解法につながります。

アルゴリズム

• 配列を初期化します。
• カウント用の変数を 0 で初期化します。
• 二重ループで配列内のすべてのペアを列挙します。
  • 各ペアに対してビット単位ORを計算します。
  • 結果が奇数であればカウントを増やします。
• カウントを返します。

C++での実装

以下は、上記のアルゴリズムをC++で実装した例です。

#include <bits/stdc++.h>
using namespace std;

int getOddPairsCount(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((arr[i] | arr[j]) % 2 != 0) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int n = 10;
    cout << getOddPairsCount(arr, n) << endl;
    return 0;
}

出力

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

35

この方法はすべてのペアを調べるため、計算量は O(n²) になります。配列のサイズが大きい場合は注意が必要です。

補足：効率的に計算する方法

「ORが奇数になるには、少なくとも一方が奇数」という性質を利用すると、配列内の奇数の個数と偶数の個数を数えるだけで、O(n) で答えを求められます。

• 奇数同士のペア：C(奇数の個数, 2) 通り
• 奇数と偶数のペア：奇数の個数 × 偶数の個数 通り

つまり、答えは odd * (odd - 1) / 2 + odd * even で計算できます。サンプル配列 {1〜10} の場合、奇数が5個・偶数が5個なので、10 + 25 = 35 となり、先ほどの実行結果と一致します。