[LeetCode]477. Total Hamming Distance

https://leetcode.com/problems/total-hamming-distance/?tab=Description

汉明距，一个数二进制表示调整多少次能变成另一个数，eg：0110 -》 1010 == 2

计算数组所有对的汉明距之和

时间O(N), 空间O(1)

计算每一位的操作次数是多少。32次遍历，计算当前位上是1的数字有多少个，是零的数字有多少个。

这里总结一下bitmanipulation：两个方向考虑，要么是遍历数组；要么是从总数组经过操作（与或非异或）之后得到的数之中32位里面下手。后一种反直觉，要多加注意

public class Solution { public int totalHammingDistance(int[] nums) { int n = nums.length; int total = 0; for (int i = 0; i < 32; i++) { int count = 0; for (int j = 0; j < n; j++) { count += (nums[j] >> i) & 1; } total += count * (n - count); } return total; } }