C++でビットごとのAND演算を使って偶数になるペアの数を数える方法

整数型の配列が与えられたとき、その配列の要素から作れるすべてのペアのうち、ビットごとのAND演算の結果が偶数になるペアの総数を求めるのがこの記事の課題です。

AND演算の真理値表

AND演算は、両方のビットが1であるときにだけ1を返します。したがって、偶数かどうかを決める最下位ビット（LSB）に注目すると、少なくとも一方が偶数であればANDの結果は必ず偶数になり、逆に奇数同士のペアだけが奇数の結果をもたらすことが分かります。この性質を利用すれば、全ペアを実際に調べることなく、効率よく答えを計算できます。

入力と出力の例

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

出力： ビットANDが偶数になるペアの数 − 7

説明：

上の表からも分かるように、10通りのペアのうち結果が奇数になるのは (5, 1)、(5, 9)、(1, 9) の3組、つまり奇数同士のペアだけであり、残りの7組はすべて偶数になっています。

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

1. ペアを作成する対象となる整数要素の配列を入力として受け取ります。
2. 配列のサイズを計算し、そのデータを処理用の関数へ渡します。
3. 配列内の奇数の個数を格納する一時変数 count を用意します。
4. FORループを i = 0 から配列サイズまで回します。
5. ループ内で arr[i] % 2 != 0（奇数である場合）なら count を1増やします。
6. count を count * (count - 1) / 2 に更新し、奇数同士の組み合わせの総数（＝AND結果が奇数になるペア数）を求めます。
7. 全ペアの総数 total_pair を size * (size - 1) / 2 で計算します。
8. total_pair から奇数ペアの数を引けば、AND結果が偶数になるペア数が求まります。
9. その値を返し、結果を出力します。

この方法では配列を一度走査するだけなので、時間計算量は O(n) となり、全ペアを二重ループで確認する O(n²) の素朴な方法よりもはるかに高速です。

サンプルコード

#include <iostream>
using namespace std;
//Count pairs with Bitwise AND as EVEN number
int count_pair(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] % 2 != 0){
            count++;
        }
    }
    count = count * (count - 1) / 2;
    int total_pair = (size * (size - 1) / 2);
    int odd = total_pair - count;
    return odd;
}
int main(){
    int arr[] = {2, 5, 1, 8, 3 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs with Bitwise-AND as even number are: "<<count_pair(arr, size) << endl;
    return 0;
}

実行結果

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

Count of pairs with Bitwise-AND as even number are: 7