【C++】ビット単位AND演算の結果が奇数になるペアの総数を数える方法

整数型の配列が与えられたとき、配列内の値から組み合わせられるすべてのペアのうち、ビット単位のAND演算（&）を適用した結果が奇数になるペアの総数を求めるのがこの記事の課題です。

AND演算の真理値表

まず、AND演算の挙動を確認しましょう。真理値表は以下の通りです。両方の入力が1のときのみ、結果が1になります。

入力例と出力例

入力 − int arr[] = {2, 5, 1, 8, 9}

出力 − ビット単位ANDの結果が奇数となるペアの数： 3

説明 − 配列内のすべてのペアについてAND演算の結果を検証すると、次のようになります。

このように、結果が奇数（最下位ビットが1）になるペアは「(5, 1)」「(5, 9)」「(1, 9)」の3組です。

アルゴリズム（プログラムで使用するアプローチ）

• ペアを形成する対象となる整数要素の配列を入力します。
• 配列のサイズを計算し、後続の処理のためにデータを関数へ渡します。
• AND演算の結果が奇数となるペアの数を格納する一時変数countを用意します。
• iを0から配列サイズまでforループで繰り返します。
• ループ内で、arr[i] % 2 == 1（要素が奇数）であればcountを1増やします。
• countに「count * (count - 1) / 2」を代入します。
• countを返します。
• 結果を出力します。

なぜ「奇数の個数」を数えるだけでよいのか

ポイントは、奇数は2進数表現において最下位ビット（LSB）が必ず1になっているという性質です。AND演算の結果が奇数になるのは、両方のオペランドのLSBが1のとき、すなわち両方の値が奇数である場合に限られます。したがって、配列中の奇数の個数をkとすれば、答えは組み合わせの公式「k × (k − 1) / 2」で一発的に求められます。これにより、全ペアを実際に列挙するO(n²)の計算量を避け、O(n)で処理できます。

コード例

#include <iostream>
using namespace std;
//ビット単位ANDの結果が奇数となるペアを数える
int count_pair(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
       if ((arr[i] % 2 == 1)){
           count++;
       }
    }
    count = count * (count - 1) / 2;
    return count;
}
int main(){
    int arr[] = {2, 5, 1, 8, 9, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs with Bitwise AND as ODD number are: "<<count_pair(arr, size) << endl;
    return 0;
}

出力

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

Count of pairs with Bitwise AND as ODD number are: 6

配列{2, 5, 1, 8, 9, 2, 7}には奇数が「5, 1, 9, 7」の4個含まれているため、4 × 3 ÷ 2 ＝ 6という結果になります。