Bit Manipulation

Leave a comment

March 10, 2017 by oneOokay

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

  • Hamming Distance : 异或 ^; 与 &; 右移 >>= N
  • Total Hamming Distance

Hamming Distance

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

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ xy < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

bit manipulation: XOR. 异或. A^B: 当A和B相同时,结果为FALSE; 当A和B不同时,结果为TRUE.

0 ^ 1 = 1;  1 ^ 0 = 1; 0 ^ 0 = 0; 1 ^ 1 = 0.

所以可以把x和y进行异或操作,得出的int就是一个值:每个bit位上如果为1的话说明A和B在该bit位上的bit是不同的,如果为0说明A和B在该bit位上的bit是相同的.

一个值和1进行”与” (&)操作 A & 1: 如果A的最后一位为1, 结果为1;如果A的最后一位为0, 结果为0. 但是对这个”与”的值的判断要加括号. (A & 1) == 1; A&1 ==1 会报错.

A >> N: 把A右移N个bit, delete掉最右的一个bit位,最左位的话如果是含符号位, 补充符号位;如果不含符号位,补充0.

public int hammingDistance(int x, int y) { 
int xor = x^y; 
int res = 0; 
while(xor!=0) { 
res+= xor & 1; 
xor >>= 1; //这个其实是: xor = xor >> 1; 
} 
return res; }
//另一个while loop loop 32次,因为int最多32位.
public int hammingDistance(int x, int y) { 
int xor = x ^ y, count = 0; 
for (int i=0;i<32;i++) 
count += (xor >> i) & 1;  //xor右移32次.
return count; }
//我写的没有用bit operation的    
public int hammingDistance(int x, int y) {
        if (x == y) return 0;
        int diff = 0;
        while (x != y){
            if (x % 2 != y % 2) diff ++;
            x = x / 2;
            y = y / 2;
        }
        return diff;
    }

 


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的个数进行统计x.
  • 得到每一个数字的最后一位的0的个数y.
  • N个数字里面有x个1和y个0,他们之间能组成的不同的pair的个数是:x * y.
    • 最后一位是否为1: (nums[i] & 1) == 1, 一定要有括号. 数字相加的时候可以不需要括号,但是判定是否为1或者0的时候要加括号.
  • 把所有的数字都右移一位 >> 1,重复第一步.
    • “<<” 左移
    • “>>” signed 带符号的右移. 如果是Integer的话, 补位0. 和>>>是一样的.
    • >>> unsigned 不带符号的右移. 补位0.

       

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: