C++での総ハミング距離

番号のリストがあるとします。与えられた数のすべてのペアのハミング距離を見つける必要があります。 2つの整数間のハミング距離は、対応するビットが異なる位置の数であることがわかっています。

したがって、入力が[4,14,17,2]の場合、出力は17になります。

これを解決するには、次の手順に従います-

• m：=1 ^ 9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（a mod m）+（b mod m））

• 関数mul（）を定義します。これにはa、b、

  が必要です。

• return（（a mod m）*（b mod m））

• 関数cntBits（）を定義します。これは、配列a、

  を取ります。

• サイズ32x2の2D配列ビットを1つ定義します

• ans：=0、n：=aのサイズ

• 初期化i：=0の場合、i

  • x：=a [i]

  • 初期化j：=0の場合、j <32の場合、更新（jを1増やします）、実行-

    • b：=（x / 2 ^ j）AND 1

    • ans：=add（ans、mul（1、bits [j、inverse of b]））

    • ビット[j、b]：=add（bits [j、b]、1）

• ansを返す

• メインの方法から、次のようにします-

• cntBits（nums）を返す

理解を深めるために、次の実装を見てみましょう-

例

#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