C++でセットビット数に基づいて配列をソートする方法

今回は、配列を「セットビット」の数に基づいてソートするという興味深い問題を取り上げます。セットビットとは、数値を2進数で表したときに「1」となっているビットのことです。セットビット数が多い要素ほど、少ない要素よりも前に配置されるように並べ替えます。

例として、12・15・7 という3つの数値を考えてみましょう。それぞれの2進数表現とセットビット数は次のとおりです。

1100 (12) → セットビット数 2
1111 (15) → セットビット数 4
0111 (7)  → セットビット数 3

これをセットビット数の降順でソートすると、結果は以下のようになります。

1111, 0111, 1100 （つまり 15, 7, 12）

解決のアプローチ

まず各数値のセットビット数を求める関数を作成し、その結果をもとにC++ STLの sort 関数で使う比較ロジックを実装します。

アルゴリズム

getSetBitCount(number):
開始
    count := 0
    number が 0 でない間、繰り返す
        if (number AND 1) = 1 ならば
            count を 1 増やす
        number を 1 ビット右シフトする
    繰り返し終了
    return count
終了

compare(num1, num2):
開始
    count1 = getSetBitCount(num1)
    count2 = getSetBitCount(num2)
    count1 <= count2 ならば false を返し、それ以外は true を返す
終了

C++での実装例

#include<iostream>
#include<algorithm>
using namespace std;

// セットビット数をカウントする関数
int getSetBitCount(int number){
    int count = 0;
    while(number){
        if(number & 1)      // 最下位ビットが1かどうか判定
            count++;
        number = number >> 1; // 1ビット右シフト
    }
    return count;
}

// セットビット数が多い方を先にする比較関数
int compare(int num1, int num2){
    int count1 = getSetBitCount(num1);
    int count2 = getSetBitCount(num2);
    return count1 > count2;
}

int main(){
    int data[] = {2, 9, 4, 3, 5, 7, 15, 6, 8};
    int n = sizeof(data)/sizeof(data[0]);
    sort(data, data + n, compare);
    for(int i = 0; i<n; i++){
        cout << data[i] << " ";
    }
}

出力結果

15 7 9 3 5 6 2 4 8

補足：より簡潔な実装方法

GCCやClangなどのコンパイラでは __builtin_popcount()、C++20以降では標準ライブラリの std::popcount() を使うことで、セットビット数を1行で取得できます。また、比較関数は return count1 > count2; のようにブール値を直接返すとコードがすっきりし、意図も明確になります。この比較関数は「セットビット数が等しい要素同士の相対的な順序は元の配列の並びに依存する」ため、安定なソートが必要な場合は stable_sort の利用も検討するとよいでしょう。