C++で同じ数のセットビットを持つ連続する配列要素の最大数を求める方法

整数要素からなるソートされていない配列が与えられたとき、次の2つの条件を満たす区間の最大長を求めるのが課題です。

• セットビット（2進表現で1になっているビット）の数が互いに等しいこと
• その要素同士が配列内で連続（隣接）していること

ここでは、C++を使ってこの問題を効率的に解く方法を、具体例とサンプルコード付きで解説します。

入力例と出力例

例1

int arr[] = { 5, 8, 1, 2, 9, 12 }

出力 − セットビット数が同じ連続する配列要素の最大数: 3

説明 − 各要素を2進数に変換し、セットビットの数を数えます。

arr[0] = 5  => 0101  => セットビット数: 2
arr[1] = 8  => 1000  => セットビット数: 1
arr[2] = 1  => 0001  => セットビット数: 1
arr[3] = 2  => 0010  => セットビット数: 1
arr[4] = 9  => 1001  => セットビット数: 2
arr[5] = 12 => 1100  => セットビット数: 2

このとき、セットビット数が同じでかつ配列内で連続しているのは「8, 1, 2」（いずれも1個）の区間で、長さは3になります。「9, 12」もセットビット数2で連続していますが長さは2なので、求める最大値は3となります。

例2

int arr[] = { 5, 8, 1, 2 }

出力 − セットビット数が同じ連続する配列要素の最大数: 3

説明 − 各要素のセットビット数はそれぞれ 5→2個、8→1個、1→1個、2→1個です。したがって「8, 1, 2」の3要素がセットビット数1で連続しており、最大長は3になります。

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

• 整数型の配列要素を入力として受け取ります。
• sizeof を使って配列のサイズを求め、処理用の関数に渡します。
• 連続長を数えるための一時変数 temp と、最大値を保持する maximum を、ともに1で初期化します。
• 各要素のセットビット数を格納するための vector を用意します。
• 配列の先頭から末尾までループを回し、「__builtin_popcount(要素)」関数でセットビット数を取得して vector に格納していきます。この関数は引数に渡された整数のセットビットの総数を返します。
• 続いて vector を先頭から走査し、隣接する要素のセットビット数が一致すれば temp を+1、一致しなければ temp を1に戻します。
• max 関数で maximum と temp を比較し、大きい方を maximum に代入して更新します。
• 最後に maximum を返し、結果を出力します。

C++実装例

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

// 同じセットビット数が連続する区間の最大長を求める関数
int maximum_SameBits(int arr[], int size){
    int temp = 1;
    int maximum = 1;
    vector<int> vec;
    // 各要素のセットビット数を vector に格納
    for (int i = 0; i < size; i++){
        vec.push_back(__builtin_popcount(arr[i]));
    }
    // 隣接する要素のセットビット数を比較して最長区間を求める
    for (int i = 1; i < (int)vec.size(); i++){
        if (vec[i] == vec[i - 1]){
            temp++;
        }
        else{
            temp = 1;
        }
        maximum = max(maximum, temp);
    }
    return maximum;
}

int main(){
    int arr[] = { 5, 8, 1, 2, 9, 12 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "同じセットビット数を持つ連続する配列要素の最大数: "
         << maximum_SameBits(arr, size);
    return 0;
}

出力

同じセットビット数を持つ連続する配列要素の最大数: 3

計算量と補足

このアルゴリズムは配列を2回走査するだけなので、時間計算量は O(n)、セットビット数を格納する vector の分だけ空間計算量も O(n) となります。

なお、__builtin_popcount はGCCなど主要なコンパイラで利用できる組み込み関数です。C++20以降では、<bit> ヘッダの標準ライブラリ関数 std::popcount を使うことで、より移植性の高いコードを書くこともできます。