<p>The <a href="https://en.wikipedia.org/wiki/Hamming_distance" target="_blank">Hamming distance</a> between two integers is the number of positions at which the corresponding bits are different.</p>

<p>Given an integer array <code>nums</code>, return <em>the sum of <strong>Hamming distances</strong> between all the pairs of the integers in</em> <code>nums</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,14,2]
<strong>Output:</strong> 6
<strong>Explanation:</strong> In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,14,4]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li>The answer for the given input will fit in a <strong>32-bit</strong> integer.</li>
</ul>

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        """
        For each bit, go through and keep running counts of set/not set, and use those to get the sum
        """
        n = len(nums)
        has_non_zero = True
        total = 0
        
        while has_non_zero:
            has_non_zero = False
            zero_bits = 0
            one_bits = 0
            
            for j in range(n):
                num = nums[j]
                bit = 1 & num
                # print(f'{num=} {bit=}')
                if bit == 1:
                    total += zero_bits
                else:
                    total += one_bits
                
                if bit == 1:
                    one_bits += 1
                else:
                    zero_bits += 1
                
                nums[j] = num >> 1
                if nums[j] > 0:
                    has_non_zero = True
        
        return total

17600