# Bit Manipulation

Leave a commentMarch 10, 2017 by oneOokay

我真的是一直在刻意回避做这种类型的题目…

Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

**Example:**

Input:4, 14, 2Output:6Explanation:In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

**Note:**

- Elements of the given array are in the range of
`0`

to`10^9`

- Length of the array will not exceed
`10^4`

.

注意求Hamming distance的话: 1 和1001之间的距离应该是1. (“0001″和”1001”)

Brutal force必定TLE,所以要用bit manipulation…

- 对所有数字的最后一位数进行统计, 统计1的个数m,从而得到0的个数n.可以组成差为1的pair数为:m*n
- 统计方法判断是否为1: (nums[i] & 1) == 1

- 把所有的数字都右移一位 >>> 1,重复第一步.

public int totalHammingDistance(int[] nums) { if(nums == null || nums.length <= 1) return 0; int totalDistance = 0; for (int i = 0; i < 32; i ++){ int totalOnes = 0; for (int j = 0; j < nums.length; j ++){ if ((nums[j] & 1) == 1) totalOnes ++; nums[j] = nums[j] >>> 1; } totalDistance += totalOnes * (nums.length - totalOnes); } return totalDistance; }

Advertisements