C++의 총 해밍 거리

<시간/>

숫자 목록이 있다고 가정합니다. 주어진 숫자 쌍의 해밍 거리를 찾아야 합니다. 두 정수 사이의 해밍 거리는 해당 비트가 다른 위치의 수라는 것을 알고 있습니다.

따라서 입력이 [4,14,17,2]와 같으면 출력은 17이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=1^9 + 7
add() 함수를 정의하면, b,
반환 ((a mod m) + (b mod m))
mul() 함수를 정의하면, b,
return ((a mod m) * (b mod m))
cntBits() 함수를 정의합니다. 이것은 배열 a,
를 취합니다.
크기가 32 x 2인 하나의 2D 배열 비트 정의
ans :=0, n :=a
의 크기
initialize i :=0의 경우, i
- x :=a[i]
- initialize j :=0의 경우 j <32일 때 업데이트(j를 1만큼 증가), 수행 -
  - b :=(x / 2^j) AND 1
  - ans :=add(ans, mul(1, bits[j, b]의 역))
  - 비트[j, b] :=add(비트[j, b], 1)
반환
주요 방법에서 다음을 수행하십시오 -
반환 cntBits(숫자)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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}