【C++】同じセットビット数を持つ数値を加算して得られる最大合計の求め方

問題文

N個の数値からなる配列が与えられたとき、同じ数のセットビット（2進数表現で「1」になっているビット）を持つ数値同士をグループ化して加算し、その中で最大となる合計値を求めるのが課題です。

例

入力配列が {2, 5, 8, 9, 10, 7} の場合、出力は 24 になります。まず各数値のセットビット数を確認してみましょう。

• 2 のセットビット数は 1（10進数: 2 → 2進数: 10）

• 5 のセットビット数は 2（2進数: 101）

• 8 のセットビット数は 1（2進数: 1000）

• 9 のセットビット数は 2（2進数: 1001）

• 10 のセットビット数は 2（2進数: 1010）

• 7 のセットビット数は 3（2進数: 111）

このうち、セットビット数が 2 である数値は 5、9、10 の3つです。これらを加算すると 5 + 9 + 10 = 24 となり、これが求める最大合計です。

アルゴリズム

• 配列を走査し、各要素のセットビット数をカウントします。

• 32ビット整数を想定し、セットビット数は最大32通りであることから、サイズ32の合計用配列を初期化します。

• 配列を反復処理し、各要素を「その要素のセットビット数」に対応するインデックスの位置に加算していきます。

• 最後に合計用配列を走査し、最大値を見つけて返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int bitCount(int n){
    int count = 0;
    while (n) {
        count++;
        n = n & (n - 1);
    }
    return count;
}
int maxSum(int arr[], int n){
    int bits[n];
    for (int i = 0; i < n; i++) {
        bits[i] = bitCount(arr[i]);
    }
    int sum[32] = { 0 };
    for (int i = 0; i < n; i++) {
        sum[bits[i]] += arr[i];
    }
    int maximum = 0;
    for (int i = 0; i < 32; i++) {
        maximum = max(sum[i], maximum);
    }
    return maximum;
}
int main(){
    int arr[] = {2, 5, 8, 9, 10, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum = " << maxSum(arr, n) << endl;
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Maximum sum = 24

コードのポイントと計算量

bitCount 関数では、Brian Kernighan のアルゴリズム（n & (n - 1) を繰り返す手法）を採用しています。この方法では、1回の演算ごとに最下位のセットビットが1つ消えるため、セットビットの数だけの反復で効率よくカウントできます。

• 時間計算量： O(N × B)。N は配列の要素数、B は各数値のビット長です。

• 空間計算量： O(1)。サイズ32の補助配列のみを使用するため、実質的に定数領域で動作します。