首页 > 代码库 > 从0开始的LeetCode生活—461-Hamming Distance(汉明距离)

从0开始的LeetCode生活—461-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 ≤ 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.

题目大意:

给你两个数字,返回这两个数字的汉明距离,汉明距离就是看两个数字的二进制代码,按位异或,比如1和4,二进制分别为(0001)和(0100),一个个异或比较后得到(0101)因为第二位和第四位不一样。然后数一下得到的数有几个1.这里有两个1,所以返回2

解法:

这是一个简单的题目,先定义一个计数器和一个记录两个数字异或的变量。即int cnt=0;int e=x^y;

然后数一下e的二进制代码里面有几个1,我的做法是让它与1按位与,如果和1按位与是1,那么就说明当前最后一位是1,如果不是,那当前最后一位为0.然后再左移,直到它变为0

比如说1和4,按位与后得到的e==5(二进制为0101)

1)与1按位与,得到1,则cnt+1;

2)右移一位,得到(010),与1按位与后得到0,则cnt不改变;

3)右移,得到(01),与1按位与得到1,cnt+1;

4)右移,得到(0),与1按位与得到0,cnt不变;

5)此时e==0,退出循环,返回cnt的值,即2.

代码:

int hammingDistance(int x, int y) {
    int r=0,e=x^y;
    while(e){
        if(e&1)
            ++r;
        e>>=1;
    }
    return r;
}

 

从0开始的LeetCode生活—461-Hamming Distance(汉明距离)