C++で総ハミング距離を求める：全ペアのビット差を効率的に計算する方法

数値のリストが与えられたとき、リスト内のすべてのペアに対するハミング距離の合計（総ハミング距離）を求めることを考えます。ハミング距離とは、2つの整数を比較した際に、対応するビットが異なる位置の個数のことです。

たとえば、入力が [4, 14, 17, 2] の場合、出力は 17 となります。

解法のアプローチ

すべてのペアを総当たりで比較すると計算量が膨大になるため、ここではビット位置ごとに着目する効率的な手法を紹介します。

あるビット位置 j に注目したとき、それまでに処理済みの数値の中で「現在の数値と逆のビット値を持つもの」の個数を順次加算していけば、最終的に全ペアのハミング距離の合計が求まります。結果が巨大な数になる可能性を考慮し、剰余 10⁹ + 7 を用いて計算を行います。

アルゴリズムの手順

• m := 10⁹ + 7 とする（剰余演算用の定数）

• add(a, b)：((a mod m) + (b mod m)) を返す関数を定義する

• mul(a, b)：((a mod m) × (b mod m)) を返す関数を定義する

• cntBits(a)：配列 a を引数にとる関数を定義する

• 32 × 2 のサイズを持つ2次元配列 bits を用意する

• ans := 0、n := 配列 a のサイズとする

• i := 0 から n - 1 まで繰り返す：

  • x := a[i]

  • j := 0 から 31 まで繰り返す：

    • b := (x ÷ 2^j) AND 1（j 番目のビットの値）

    • ans := add(ans, mul(1, bits[j][!b]))（逆のビットを持つ過去の数の個数を加算）

    • bits[j][b] := add(bits[j][b], 1)（現在のビット値の出現回数を更新）

• ans を返す

• main 関数からは cntBits(nums) の結果を返す

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
    public:
    lli add(lli a, lli b){
        return ((a % m) + (b % m));
    }
    lli mul(lli a, lli b){
        return ((a % m) * (b % m));
    }
    int cntBits(vector<int>& a){
        vector<vector<lli> > bits(32, vector<lli>(2));
        lli ans = 0;
        int n = a.size();
        for (int i = 0; i < n; i++) {
            lli x = a[i];
            for (lli j = 0; j < 32; j++) {
                lli b = (x >> j) & 1;
                ans = add(ans, mul((lli)1, bits[j][!b]));
                bits[j][b] = add(bits[j][b], (lli)1);
            }
        }
        return ans;
    }
    int totalHammingDistance(vector<int>& nums){
        return cntBits(nums);
    }
};
main(){
    Solution ob;
    vector<int> v = {4,14,17,2};
    cout << (ob.totalHammingDistance(v));
}

入力

{4,14,17,2}

出力

17

計算量について

このアルゴリズムは、各数値について最大32ビット分の走査を行うだけなので、時間計算量は O(n × 32)、空間計算量は O(1) で抑えられます。全ペアを直接比較する O(n²) の総当たり方式と比べ、特に n が大きい場合に大幅な高速化を実現できます。