461. Hamming Distance

1. Description:

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 ≤ x, y < 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.

2. Difficulty:

Easy

3. Solution:

bit count

What does come to your mind first when you see this sentence "corresponding bits are different"? Yes, XOR! Also, do not forget there is a decent function Java provided: Integer.bitCount() ~~~

But how does bitcount work?

Let us look at the source code

public static int bitCount(int i) {
        // HD, Figure 5-2
//        java 逐位运算符
//        逐位或运算符(|),右移运算符(>>)非运算符(~) ,用0补足的右移运算符(>>>)
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

hex: 0x55555555, hex 5: 0101

binary: 101 0101 0101 0101 0101 0101 0101 0101

i = i - ((i >>> 1) & 0x55555555);

第一行是计算每两位中的 1 的个数 , 并且用该对应的两位来存储这个个数 ,
如 : 01101100 -> 01011000 , 即先把前者每两位分段 01 10 11 00 , 分别有 1 1 2 0 个 1, 用两位二进制数表示为 01 01 10 00, 合起来为 01011000.

Count the number of 1 in every two digits, and use two digits to store it.

e.g. 01 10 11 00 store in 01 01 10 00.

By (i >>> 1) e.g. 01 10 >>> 1 = 00 11 , 00 11 & 0x5(01 01) = 00 01 . We get the number of 1 in high digit in 01 10 .

• In first two digits01, the number of 1 in high digit is 0.

• In second two digits10, the number of 1 in high digit is 1.

Then how to get total number of every 2 digits?

All cases:

11 , i >>> 1 = 1 , 1 & 0101 = 1 . We suppose to get 10 . And 11 - 1 = 10 .

10 , i >>> 1 = 1 , 1 & 0101 = 1 . We suppose to get 01 . And 10 - 1 = 01 .

01 , i >>> 1 = 0 , 0 & 0101 = 0 . We suppose to get 01 . And 01 - 0 = 01 .

00 , i >>> 1 = 0 , 0 & 0101 = 0 . We suppose to get 00 . And 00 - 0 = 00 .

So i - 00 01 = 01 10 - 00 01 = 01 10.

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

0x33333333 = 0011 0011 0011…

第二行是计算每四位中的 1 的个数 , 并且用该对应的四位来存储这个个数 .
如 : 01101100 经过第一行计算后得 01011000 , 然后把 01011000 每四位分段成 0101 1000 , 段内移位相加 : 前段01+01 =10 , 后段 10+00=10, 分别用四位二进制数表示为 0010 0010, 合起来为 00100010 .

After counting every two digits. We should count every 4 digits.

It is quite same like count every two digits. Try it!

i = (i + (i >>> 4)) & 0x0f0f0f0f;

0f0f0f0f = 0000 1111 0000 1111 0000 1111

After count 4 digits. We count 8 digits.

We still check 16digits and 32 digits.

other solution1:

public int hammingDistance_2(int x, int y) {
//        对于一个正整数如果是偶数，该数的二进制数的最后一位是 0 ，
// 反之若是奇数，则该数的二进制数的最后一位是 1 。因此，可以考虑利用位移、判断奇偶来实现。
        int xor = x ^ y;
        int count = 0;
        while (xor != 0)
        {
            if((xor & 1) == 1){
                count++;
            }
            xor = xor >>> 1;
        }
        return count;
    }

other solution2:

public int hammingDistance_3(int x, int y) {
// 计算 1 的个数，若让算法的运算次数只与“ 1 ”的个数有关，那复杂度就能进一步降低。
// 思想： x & (x-1) 可以消去 x 二进制数的最后一位 1
        int xor = x ^ y;
        int count = 0;
        while (xor != 0)
        {
            xor &= xor - 1;
            count++;
        }
        return count;
    }

http://15838341661-139-com.iteye.com/blog/1642525