Can anyone help me understand why sum of hamming distance of all pair of elements equals 2XY?


#1

I don’t understand why sum of hamming distance of all pair of elements equals 2XY, Can anyone help me understand this with an example?


#2

It’s basic P&C.
No. of ways of selecting num with set bit = x
No. of ways of selecting num with unset bit = y
No. of ways of arranging two numbers = 2
Answer = x * y * 2


#3

Let X = the set of integers with 1 bit in position k.
Let Y = the set of integers with 0 bit in position k.
Considering only position k, the hamming distance between elements of set X is 0 and similarly for Y.
The hamming distance between an element of X and an element of Y is 1.

For each element in X, there are |Y| elements that can be paired with it to get a hamming distance of 1. So the sum of the hamming distances is |X| x |Y|.
For each element in Y, there are |X| elements that can be paired with it to get a hamming distance of 1. So the sum of the hamming distances is |Y| x |X|.
The total sum of hamming distances is 2 x |X| x |Y|.