C++で配列内の「セットビット数が等しいペア」をカウントする方法

問題概要

整数型の要素からなる配列が与えられます。この配列から作れるすべてのペアについて、それぞれの要素が持つセットビット(2進表現で「1」となるビット)の数を計算し、両方の要素のセットビット数が等しいペアがいくつあるかを求めるのが本記事の課題です。

整数値を2進数に変換すると、0と1の組み合わせで表現されます。このうち値が「1」になっているビットのことを、コンピュータの用語ではセットビットと呼びます。たとえば、6は2進数で「110」と表されるため、セットビットは2個です。

入出力例

例1

入力:

int arr[] = {6, 5, 1, 3, 7}

出力:

Count of pairs in an array such that both elements has equal set bits are: 3

説明:

配列 {6, 5, 1, 3, 7} から作れるペアと、それぞれのセットビット数は以下の通りです。

• (6, 5): 6 → 2個、5 → 2個(有効なペア)
• (6, 1): 6 → 2個、1 → 1個(無効)
• (6, 3): 6 → 2個、3 → 2個(有効なペア)
• (6, 7): 6 → 2個、7 → 3個(無効)
• (5, 1): 5 → 2個、1 → 1個(無効)
• (5, 3): 5 → 2個、3 → 2個(有効なペア)
• (5, 7): 5 → 2個、7 → 3個(無効)
• (1, 3): 1 → 1個、3 → 2個(無効)
• (1, 7): 1 → 1個、7 → 3個(無効)
• (3, 7): 3 → 2個、7 → 3個(無効)

したがって、セットビット数が等しい有効なペアは (6, 5)、(6, 3)、(5, 3) の3つです。

例2

入力:

int arr[] = {4, 6, 3, 2}

出力:

Count of pairs in an array such that both elements has equal set bits are: 2

説明:

• (4, 6): 4 → 1個、6 → 2個(無効)
• (4, 3): 4 → 1個、3 → 2個(無効)
• (4, 2): 4 → 1個、2 → 1個(有効なペア)
• (6, 3): 6 → 2個、3 → 2個(有効なペア)
• (6, 2): 6 → 2個、2 → 1個(無効)
• (3, 2): 3 → 2個、2 → 1個(無効)

したがって、有効なペアは (4, 2) と (6, 3) の2つです。

アルゴリズム(アプローチ)

このプログラムでは、以下の手順で問題を解きます。

1. 整数要素の配列を入力として受け取り、配列のサイズを計算して関数に渡します。
2. セットビット数が等しいペアの個数を格納するための一時変数 count を宣言します。
3. 外側のループで i を 0 から配列サイズまで回します。
4. 内側のループで j を i + 1 から配列サイズまで回し、重複しないすべてのペアを生成します。
5. ループ内で、GCC拡張の組み込み関数 __builtin_popcount(要素) を呼び出し、整数のセットビットの総数を取得して、ペアの1つ目・2つ目の要素のセットビット数とします。
6. 1つ目と2つ目の要素のセットビット数が等しい場合は、count を1増やします。
7. ループ終了後、count を返します。
8. 結果を出力します。

なお、__builtin_popcount() はGCCやClangで利用できる組み込み関数です。C++20以降では、標準ライブラリの std::popcount()(ヘッダー <bit>)を使うこともできます。

サンプルコード

#include <iostream>
using namespace std;
int pair_setBit(int arr[], int size){
    int count = 0;
    for(int i = 0 ;i <size ; i++){
        for(int j = i+1; j<size; j++){
            int first = __builtin_popcount(arr[i]);
            int second = __builtin_popcount(arr[j]);
            if(first == second){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {6, 5, 1, 3, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs in an array such that both elements has equal set bits are: "<<pair_setBit(arr, size);
    return 0;
}

実行結果

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

Count of pairs in an array such that both elements has equal set bits are: 3

計算量

すべてのペアを二重ループで調べるため、時間計算量は O(n²) です。一方、追加で必要なメモリはカウンタ程度のみなので、空間計算量は O(1) となります。要素数が多い場合は、セットビット数ごとに出現回数を集計して組み合わせを計算する方法(O(n))に置き換えると、さらに効率化できます。