C ++中的总汉明距离

假设我们有一个数字列表。我们必须找到所有给定数字对的汉明距离。我们知道两个整数之间的汉明距离是相应位不同的位置数。

因此，如果输入类似于[4,14,17,2]，则输出将为17。

为了解决这个问题，我们将遵循以下步骤-

• m：= 1 ^ 9 + 7

• 定义一个函数add()，这将需要a，b，

• 返回（（a mod m）+（b mod m））

• 定义一个函数mul()，这将需要a，b，

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

• 定义一个函数cntBits()，它将使用一个数组，

• 定义一个大小为32 x 2的2D数组位

• ans：= 0，n：= a的大小

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

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

• ans：= add（ans，mul（1，bits [j，b的倒数]））

• 位[j，b]：=添加（位[j，b]，1）

• x：= a [i]

• 对于初始化j：= 0，当j <32时，更新（将j增加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