汉明距离（位运算，清晰图解）

科技前沿 • 2025-02-17 10:08 • 阅读 32

大家好，我是讯享网，很高兴认识大家。

题目

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

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意： 0 ≤ x, y < 2^31.

示例:

讯享网

解题思路

要找出两个整数对应二进制位不同的位置的数目，对 位运算 有所了解的童鞋，应该会很自然地想到位运算中的 按位异或，通过将两个整数对应二进制位 按位异或（同一位置，元素相同异或得 0 或者得 1） 找到其二进制不同的位置，找到之后，只需要统计异或的结果中 1 的个数即可。

举栗

以示例为栗，如下图示：

元素值及其对应的二进制

异或之后的结果

统计整数的二进制表达中 1 的个数

以上面 x ^ y 的结果为栗，统计 x ^ y 中 1 的个数

cnt 记录 x ^ y 中 1 的个数

方法一 ：通过不断右移获取末尾位统计二进制中 1 的个数

第一次

x ^ y 右移一位

右移末尾为 0 继续右移

第二次

x ^ y 继续右移一位

此时 x ^ y == 0，无需再右移。

方法二 ：通过 n & (n - 1) 统计二进制中 1 的个数

还是以上面的 x ^ y 的结果为栗，统计 x ^ y 中 1 的个数，假设 n = x ^ y

第一次

第二次

此时 n & (n - 1) == 0，统计完成。

Show me the Code

c 语言

int hammingDistance(int x, int y){   int cnt = 0;   int z = x ^ y;   while (z != 0) {     cnt += z & 1;     z = z>>1;   }      return cnt; }

讯享网

c++

讯享网int hammingDistance(int x, int y) {     int cnt = 0;     int z = x ^ y;     while (z != 0) {         cnt++;         z &= (z - 1);     }     return cnt; }

python3

class Solution:     def hammingDistance(self, x: int, y: int) -> int:         cnt, z = 0, x ^ y         while z != 0:             cnt += 1             z = z & (z - 1)                      return cnt

golang

讯享网func hammingDistance(x int, y int) int {     cnt, z := 0, x ^ y     for z != 0 {         cnt++         z &= z - 1     }          return cnt }

往期精彩回顾

决定你是否能进字节的几道题