Total Hamming Distance

The Hamming distance between two whole numbers is the number of bit positions where their binary forms differ: 4 (100) and 7 (111) differ in two positions, so their distance is 2. Write total_hamming(nums) that returns the sum of the Hamming distances of every pair of positions i < j in the list.

Examples

total_hamming([1, 2, 3])  # returns 4
total_hamming([0, 15])    # returns 4
total_hamming([5, 5, 5])  # returns 0

In the first example the pairs are 1 and 2 (01 and 10, distance 2), 1 and 3 (01 and 11, distance 1) and 2 and 3 (10 and 11, distance 1), so the total is 4.

Constraints

• 0 <= len(nums) <= 50,000
• 0 <= nums[i] <= 10**9
• With 50,000 numbers there are more than a billion pairs, too many to compare one by one.