leetcode-go/leetcode/medium/477.total-hamming-distance.go

func totalHammingDistanceSlow(nums []int) (dist int) {
	n := len(nums)
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			dist += bits.OnesCount32(uint32(nums[i] ^ nums[j]))
		}
	}
	return
}

func totalHammingDistance(nums []int) (dist int) {
	n := len(nums)
	for b := 1 << 31; 1 <= b; b >>= 1 {
		k := 0
		for _, i := range nums {
			if b&i == 0 {
				k++
			}
		}
		dist += k * (n - k) // At pos b, k 0s and n-k 1s inc k*(n-k) dist
	}
	return
}