欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leadcode的Hot100系列--461. 汉明距离

程序员文章站 2022-05-15 13:32:38
求两个数的二进制位不同的位置,最先想到的就是 异或操作 , 异或:按位运算,相同为0,不同为1。 比如: a = 6 对应的二进制表示为: 0 0 1 1 1 ​ b = 9 对应的二进制表示为: 0 1 0 0 1 则 a ^ b = 14 对应的二进制表示为: 0 1 1 1 0 所以,只要算出 ......

求两个数的二进制位不同的位置,最先想到的就是异或操作

异或:按位运算,相同为0,不同为1。

比如:
a = 6 对应的二进制表示为: 0 0 1 1 1
​ b = 9 对应的二进制表示为: 0 1 0 0 1
则 a ^ b = 14 对应的二进制表示为: 0 1 1 1 0
所以,只要算出异或之后的数的二进制表示方法里面1的个数。
比如,对于上面的异或之后为14,14的二进制里面1的个数为3,那么汉明距离就是3。
想知道是否有1,最快的当然还是位与操作

与:按位运算,相当于乘法,0与0是0,1与0是0,0与1是0,1与1是1。

所以,任何值与1相与,得到的就是就是原值二进制的最后一位
要么是1,要么是0,
这样就能得到原值的最低位是否是1。
然后再把原值整体右移一位,再查看最低位是否是1,
循环往复,就能够算出原值二进制里面1的个数了。
附上代码:

int hammingdistance(int x, int y){
    int idistance = 0;
    unsigned int uixor;
    uixor = x ^ y;
    while (uixor > 0)
    {
        if (uixor & 1)
        {
            idistance ++;
        }
        uixor >>= 1;
    }
    return idistance;
}