汉明距离( LeetCode 461 )

一、题目描述

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

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

示例 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 <= 231 – 1

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 汉明距离( LeetCode 461 ):https://leetcode-cn.com/problems/hamming-distance/
class Solution {
    public int hammingDistance(int x, int y) {

        // 将 x 与 y 执行一个异或操作
        // 异或的特征:不同为 1 ,相同为 0 
        // 这样,s 的二进制中 1 的个数就是这两个数字对应二进制位不同的位置的数目
        int s = x ^ y;

        // 统计 s 上 1 的个数
        int count = 0;

        while (s != 0) {
            // 每次让 s 与 s - 1 执行相与操作
            s &= s - 1;
            // 每循环一次,都会删去其二进制表示中最右侧的 1,最终循环的次数即为 s 中 1 的个数
            count++;
        }

        // 返回结果
        return count;
    }
}

2、C++ 代码

3、Python 代码

四、动画理解(没有声音)