461.汉明距离

LeetCode LeetCode 位运算

发布时间 : 2000-01-10 04:06

字数:1.3k 阅读 :

评论:

461.汉明距离

461.汉明距离

461.1 题目

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

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

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

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

提示：

0 <= x, y <= 2^31 - 1

461.2 题解

方法一：异或运算后统计位为1的个数

思路

先计算 x 和 y 的异或结果，异或结果中 1 的个数就是汉明距离。通过循环右移并检查最低位是否为 1 来统计。

核心思想：异或后不同的位变为 1，统计 1 的个数。

具体步骤：

计算 xorResult = x ^ y。
循环遍历 xorResult 的每一位：
- 如果最低位为 1：count++
- 右移一位
返回 count。

举例：对于 x = 1, y = 4：

xorResult = 1 ^ 4 = 5（二进制 0101）
0101 & 1 = 1，count=1，右移得 0010
0010 & 1 = 0，右移得 0001
0001 & 1 = 1，count=2，右移得 0000
结果：2

复杂度分析

时间复杂度：O(log n)，n 为较大数的值，需要遍历所有位。
空间复杂度：O(1)，只使用常数变量。

代码

// 方法一：异或运算后统计位为1的个数
static int HammingDistance1(int x, int y)
{
    // 计算两个整数的异或结果
    int xorResult = x ^ y;

    // 初始化计数器，用于统计异或结果中位为1的个数
    int count = 0;

    // 循环遍历异或结果的每一位
    while (xorResult > 0)
    {
        // 判断当前位是否为1，如果是，计数器加1
        count += xorResult & 1;

        // 右移异或结果，处理下一位
        xorResult >>= 1;
    }

    // 返回计数器的值，即汉明距离
    return count;
}

方法二：Brian Kernighan 算法

利用 x & (x - 1) 可以消除最右边的 1 这一性质。每次执行该操作并计数，直到结果为 0。操作次数即为 1 的个数，比逐位检查更高效。

复杂度分析：

时间复杂度：O(k)，k 为 1 的个数，最坏情况 O(log n)。
空间复杂度：O(1)，只使用常数变量。

// 方法二：Brian Kernighan 算法
// 通过x = x & (x - 1)把2进制数最右侧的1变为0 然后计数加1
// 比如
//   11010100   (x)
// & 11010011   (x - 1)
// -----------
//   11010000
// 每次搞掉一个1 有多少个1代表有多少不同
static int HammingDistance2(int x, int y)
{
    // 计算两个整数的异或结果
    int xorResult = x ^ y;

    // 初始化计数器，用于统计位为1的个数
    int count = 0;

    // 使用 Brian Kernighan 算法统计位为1的个数
    while (xorResult > 0)
    {
        // 将最右边的1置为0，每执行一次这个操作，计数器加1
        xorResult &= (xorResult - 1);

        // 统计位为1的个数
        count++;
    }

    // 返回计数器的值，即汉明距离
    return count;
}

461.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 计算两个整数的汉明距离，即对应二进制位不同的位置的数目。

        // 示例 1：
        // 输入：x = 1, y = 4
        // 输出：2
        // 解释：
        // 1   (0 0 0 1)
        // 4   (0 1 0 0)
        //       ↑   ↑
        // 上面的箭头指出了对应二进制位不同的位置。

        // 示例 2：
        // 输入：x = 3, y = 1
        // 输出：1

        // 提示：
        // 0 <= x, y <= 2^31 - 1

        #endregion

        #region 测试

        // 示例 1
        int x1 = 1, y1 = 4;
        int result1 = HammingDistance1(x1, y1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = HammingDistance2(x1, y1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int x2 = 3, y2 = 1;
        int result2 = HammingDistance1(x2, y2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = HammingDistance2(x2, y2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：异或运算后统计位为1的个数
    static int HammingDistance1(int x, int y)
    {
        // 计算两个整数的异或结果
        int xorResult = x ^ y;

        // 初始化计数器，用于统计异或结果中位为1的个数
        int count = 0;

        // 循环遍历异或结果的每一位
        while (xorResult > 0)
        {
            // 判断当前位是否为1，如果是，计数器加1
            count += xorResult & 1;

            // 右移异或结果，处理下一位
            xorResult >>= 1;
        }

        // 返回计数器的值，即汉明距离
        return count;
    }

    // 方法二：Brian Kernighan 算法
    // 通过x = x & (x - 1)把2进制数最右侧的1变为0 然后计数加1
    // 比如
    //   11010100   (x)
    // & 11010011   (x - 1)
    // -----------
    //   11010000
    // 每次搞掉一个1 有多少个1代表有多少不同
    static int HammingDistance2(int x, int y)
    {
        // 计算两个整数的异或结果
        int xorResult = x ^ y;

        // 初始化计数器，用于统计位为1的个数
        int count = 0;

        // 使用 Brian Kernighan 算法统计位为1的个数
        while (xorResult > 0)
        {
            // 将最右边的1置为0，每执行一次这个操作，计数器加1
            xorResult &= (xorResult - 1);

            // 统计位为1的个数
            count++;
        }

        // 返回计数器的值，即汉明距离
        return count;
    }

    #endregion
}

461.4 运行结果

示例1 方法1 输出：2
示例1 方法2 输出：2
示例2 方法1 输出：1
示例2 方法2 输出：1

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com