重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

C++求解汉明距离-创新互联

目录
  • 汉明距离介绍
  • 汉明距离应用
  • 解法1:Brian Kernighan算法
  • 解法2
  • 解法3

成都创新互联公司从2013年成立,是专业互联网技术服务公司,拥有项目做网站、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元克州做网站,已为上家服务,为克州各地企业和个人服务,联系电话:18982081108
汉明距离介绍

leetcode 461 汉明距离,难度:简单

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y,计算并返回它们之间的汉明距离。

示例 1:

输入:x = 1, y = 4
输出:2
解释:
1 (0 0 0 1)
4 (0 1 0 0)

对应二进制位不同的位置个数为2

示例 2:

输入:x = 3, y = 1
输出:1

提示:

0<= x, y<= 231 - 1

汉明距离应用

汉明距离广泛应用于多个领域。在编码理论中用于错误检测,在信息论中量化字符串之间的差异。

两个整数之间的汉明距离是对应位置上数字不同的位数。

解决此题,可以使用异或运算,当对应的二进制为不同时,输出为1,然后统计异或后1的个数。

统计二进制中1的个数,主要有3种方法:

  • Brian Kernighan算法,
  • 移位运算
  • 直接使用系统API.

下面分别介绍这3种算法

解法1:Brian Kernighan算法

Brian Kernighan算法可以用于清除二进制数中最右侧的1。Brian Kernighan算法的做法是先将当前数减一,然后在与当前数进行按位与运算。

x=x&(x-1)

示意图
在这里插入图片描述
x&(x-1)的结果变成了1110

利用此算法我们可以统计一个数字的二进制中的1的个数,即一比特数:

#includeusing namespace std;

int oneCounts(int num) {int ones = 0;

    while (num >0) {num &= num - 1;
        ones++;
    }

    return ones;
}

int main()
{int num = 23;  // 1 0111

    cout<< oneCounts(num)<< endl;

    return 0;
}

对应的此题的解法

class Solution {public:
    int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;
        while (s) {s &= s - 1;
            ret++;
        }
        return ret;
    }
};

复杂度分析

时间复杂度:O(logC),其中 C 是元素的数据范围;
空间复杂度:O(1)。

确实简单,简单的前提是得知道Brian Kernighan算法.

解法2

不知道Brian Kernighan算法也可以解决。
使用异或运算,记 s = x⊕y,我们可以不断地检查 s 的最低位,如果最低位为 1,那么令计数器加一,然后我们令 s 整体右移一位,这样 s 的最低位将被舍去,原本的次低位就变成了新的最低位。我们重复这个过程直到 s=0 为止。这样计数器中就累计了 s 的二进制表示中 1 的数量。

代码

class Solution {public:
    int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;
        while (s) {ret += s & 1;
            s >>= 1;
        }
        return ret;
    }
};

代码说明s&1, 如果最末位是1,那么s&1 = 1, ret += 1,否则ret += 0, 然后s右移一位。

解法3

使用系统内置API: __builtin_popcount, 该函数可以统计二进制数中1的个数,但是仅在gcc/g++下可使用。
代码

#includeusing namespace std;

class Solution {public:
    int hammingDistance(int x, int y) {return __builtin_popcount(x ^ y);
    }
};

int main(){Solution s;

    cout<< s.hammingDistance(1, 4)<< endl;

    return 0;
}

虽然这是一道简单题,但是并不简单,leetcode没哪道题简单。

本文参考资料
(1)https://leetcode.cn/problems/hamming-distance
(2)https://zhuanlan.zhihu.com/p/498119781

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享标题:C++求解汉明距离-创新互联
文章源于:http://cqcxhl.com/article/hesho.html

其他资讯

在线咨询
服务热线
服务热线:028-86922220
TOP