# 477. Total Hamming Distance

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FKoCVBpvN3xWZ3R8MTzCF%2F%E5%9C%96%E7%89%87.png?alt=media\&token=cd500bf3-d5bf-4ddc-bd5c-a9c4ceebe511)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F9WoUOmETcII9IclTOZUV%2Fimage.png?alt=media\&token=2692e757-2a3e-4ca0-b727-bff1a2fbe8d6)

time:O(30\*n), n is nums array length

space:O(1)

```java
// Hamming Distance - which the corresponding bits are different. so only count 0 and 1's count

class Solution {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length;
        int res = 0;
        
        for (int i = 0; i < 30; i++) { // 10^9 < 2^30...恩...shif 0~29次 bit
            int c = 0;
            for (int num : nums) {
                c += (num >> i) & 1; // calculate, how many 1 in index i
            }
            // n-c is 0's count
            res += c*(n-c); // 1 and 0's combination is the result , add i bit (0~29), 30 times
        }
        return res;
    }
}
```
