C++でKビット異なる配列のペア数を数える方法

はじめに

この記事では、配列内の要素ペアのうち、2進表現においてKビットだけ異なるペアの総数を求めるC++プログラムについて解説します。

具体的には、整数の配列と整数Kが与えられたとき、任意の2つの要素を比較し、異なるビットの数がちょうどK個になるペアがいくつ存在するかを計算します。

解決のアプローチ

この問題は、XOR(排他的論理和)の性質を利用することでシンプルに解けます。

• 配列内のすべてのペア(arr[i], arr[j])について、2つの値のXORを計算します。
• XORの結果に含まれる「1」のビット数(セットビット数)を数えます。これは2つの要素間で異なるビットの数に一致します。
• セットビット数がKと等しければ、そのペアをカウントします。

C++での実装例

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

// 2進表現におけるセットビット数を数える
int count_bit(int n){
    int count = 0;
    while (n) {
        if (n & 1)
            ++count;
        n >>= 1;
    }
    return count;
}

// Kビット異なるペアの数を数える
long long count_pair(int arr[], int n, int k) {
    long long ans = 0;
    for (int i = 0; i < n-1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int xoredNum = arr[i] ^ arr[j];
            if (k == count_bit(xoredNum))
                ++ans;
        }
    }
    return ans;
}

int main() {
    int k = 2;
    int arr[] = {2, 4, 1, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Total pairs for k = " << k << " are " << count_pair(arr, n, k) << "\n";
    return 0;
}

出力結果

5

コードの解説

count_bit関数: 引数で受け取った整数の2進表現に含まれる「1」のビット数を数えます。値を右シフトしながら、最下位ビットが1かどうかを順番に判定していきます。

count_pair関数: 二重ループで配列内のすべてのペアを走査します。各ペアのXORを計算し、そのセットビット数がKと一致した場合のみカウントを増やします。時間計算量はO(n²)です。

出力の検証: 配列{2, 4, 1, 3, 1}の2進表現はそれぞれ「10」「100」「1」「11」「1」です。たとえば2(10)と4(100)のXORは110となり、セットビット数は2のためK=2の条件を満たします。このようなペアをすべて数えると、合計5ペアになります。

まとめ

XOR演算とセットビットのカウントを組み合わせることで、Kビット異なるペアの数を簡単に求められます。ただし本手法はO(n²)の計算量となるため、要素数が非常に多い配列を扱う場合は、Trie(トライ)木などを活用した最適化手法の導入も検討するとよいでしょう。