Tổng khoảng cách Hamming trong C ++

Giả sử chúng ta có một danh sách các số. Chúng ta phải tìm khoảng cách Hamming của tất cả các cặp số đã cho. Chúng ta biết rằng khoảng cách Hamming giữa hai số nguyên là số vị trí tại đó các bit tương ứng khác nhau.

Vì vậy, nếu đầu vào là [4,14,17,2], thì đầu ra sẽ là 17.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

m:=1 ^ 9 + 7
Xác định một hàm add (), điều này sẽ lấy a, b,
return ((a mod m) + (b mod m))
Xác định một hàm mul (), điều này sẽ nhận a, b,
return ((a mod m) * (b mod m))
Xác định một hàm cntBits (), điều này sẽ lấy một mảng a,
Xác định một bit mảng 2D có kích thước 32 x 2
ans:=0, n:=kích thước của một
để khởi tạo i:=0, khi i
- x:=a [i]
- để khởi tạo j:=0, khi j <32, cập nhật (tăng j lên 1), thực hiện -
  - b:=(x / 2 ^ j) VÀ 1
  - ans:=add (ans, mul (1, bits [j, nghịch đảo của b]))
  - bits [j, b]:=add (bits [j, b], 1)
trả lại ans
Từ phương thức chính, hãy làm như sau -
trả về cntBits (nums)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

{4,14,17,2}

Tổng khoảng cách Hamming trong C ++

Ví dụ

Đầu vào

Đầu ra