Hamming distance between two non-negative integers is defined as the number of positions at which the corresponding bits are different.
For example,
HammingDistance(2, 7) = 2, as only the first and the third bit differs in the binary representation of 2(010) and 7 (111).
Given an array of N non-negative integers, find the sum of hamming distances of all pairs of integers in the array. Return the answer modulo 1000000007.
public class Solution { // DO NOT MODIFY THE LIST. IT IS READ ONLY public int hammingDistance(final List<Integer> A) { int d = 0; for (int i = 0; i < A.size(); i ++) { int a = A.get(i); for (int j = i + 1; j < A.size(); j ++) { int b = A.get(j); d += countSetBits(a ^ b); } } return (d * 2) % 1000000007; }
private int countSetBits(int n) { int count = 0; while (n != 0) { count += n & 1; n >>= 1; } return count; } }
public class Solution { // DO NOT MODIFY THE LIST. IT IS READ ONLY public int hammingDistance(final List<Integer> A) { long d = 0; long n = A.size(); for (int i = 0; i < 32; i ++) { long ones = 0; for (int j = 0; j < n; j ++) { int v = A.get(j); ones += (v >> i) & 1; } d += ones * (n - ones) * 2; } return (int) (d % 1000000007); } }