C++でセットビット数がKと等しい配列の全要素のXORを求める方法

この記事では、n個の要素からなる整数型配列と整数値kが与えられたとき、「セットビット(値が1になっているビット)の数がkと一致する要素」だけを抜き出し、それらすべてのXOR(排他的論理和)を求める方法を解説します。

問題の例

入力

array = {2, 12, 44, 103, 17} , K = 3

出力

44

まず、各要素を二進数で表し、セットビットの数を確認してみましょう。

• 2 → 二進数「10」→ セットビット数:1
• 12 → 二進数「1100」→ セットビット数:2
• 44 → 二進数「101100」→ セットビット数:3
• 103 → 二進数「1100111」→ セットビット数:5
• 17 → 二進数「10001」→ セットビット数:2

この中でセットビット数が3(kと一致)なのは「44」だけなので、答えは44となります。

解決のためのアプローチ

この問題は、次の手順で解くことができます。

1. 配列内の各要素について、セットビットの数を数える。
2. セットビット数がkと一致する要素をvectorに格納する。
3. vector内のすべての要素のXORを計算し、結果として返す。

セットビット数のカウントには、C++の組み込み関数である__builtin_popcount()を使用します。この関数は、引数に渡した整数値のセットビット数を返してくれるため、自前でビット演算を実装する必要がなく、簡潔かつ高速に処理できます。

C++による実装例

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

int XorKSetBits(int arr[], int n, int k){
    vector<int> kBitElements;
    // 各要素のセットビット数を調べ、kと一致するものを格納
    for (int i = 0; i < n; i++) {
        if (__builtin_popcount(arr[i]) == k) {
            kBitElements.push_back(arr[i]);
        }
    }
    // 格納した要素のXORを計算
    int result = kBitElements[0];
    for (int i = 1; i < kBitElements.size(); i++)
        result ^= kBitElements[i];
    return result;
}

int main(){
    int arr[] = { 2, 12, 44, 103, 17 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout<<"セットビット数が "<<k<<" 個である配列要素のXOR : "<<XorKSetBits(arr, n, k);
    return 0;
}

出力

セットビット数が 3 個である配列要素のXOR : 44

まとめ

本記事では、セットビット数がkと一致する配列要素のXORを求める方法を紹介しました。ポイントは以下の2点です。

• __builtin_popcount() を使うことで、セットビット数を簡単に取得できる。
• 条件に合致する要素を一旦vectorに集めてからXORを計算することで、ロジックが明快になる。

計算量は、配列の要素数をnとすると O(n) であり、非常に効率的です。ビット演算を扱う他の問題にも応用できるテクニックなので、ぜひ覚えておきましょう。