Bit Manipulation

Leave a comment

March 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, 2

Output: 6

Explanation: 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:

  1. Elements of the given array are in the range of 0 to 10^9
  2. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: