461.汉明距离

LeetCode LeetCode 位运算

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

字数:1.1k 阅读 :

评论:

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的个数

// 方法一：异或运算后统计位为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;

    //也可以转成二进制遍历
    int calResult = x ^ y;

    string binary = Convert.ToString(calResult, 2);

    int result = 0;

    foreach (var c in binary)
    {
        if (c == '1')
        {
            result++;
        }
    }

    return result;
}

Brian Kernighan 算法

// 方法二：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;

        //也可以转成二进制遍历
        int calResult = x ^ y;

        string binary = Convert.ToString(calResult, 2);

        int result = 0;

        foreach (var c in binary)
        {
            if (c == '1')
            {
                result++;
            }
        }

        return result;
    }

    // 方法二：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