What is the Hamming distance?

The Hamming distance is the number of positions at which the corresponding bits of two integers differ.

How can I solve this problem using bitwise operations?

You can solve this problem using the XOR operator, which compares bits and sets differing bits to 1. Counting the number of 1s in the result gives the Hamming distance.

How do I optimize my solution for larger inputs?

Optimizing the solution involves using efficient algorithms like Brian Kernighan’s algorithm to count set bits in the XOR result, reducing the number of operations.

What are some common mistakes to avoid in this problem?

One common mistake is using a method like converting numbers to binary strings, which is less efficient than bitwise manipulation. Another mistake is not counting the 1s in the XOR result correctly.

Why is the XOR operation useful for Hamming distance?

The XOR operation highlights the positions where two integers differ by setting those bits to 1. This makes it easy to count the differences by simply counting the 1s in the XOR result.

#461

Easy

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y ，计算并返回它们之间的汉明距离。示例 1：输入： x = 1, y = 4 输出： 2 解释： 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。示…

位运算

题目描述

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

给你两个整数 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³¹ - 1

注意：本题与 2220. 转换数字的最少位翻转次数相同。

lightbulb

解题思路

方法一：位运算

我们将 $x$ 和 $y$ 按位异或，得到的结果中的 $1$ 的个数就是汉明距离。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return (x ^ y).bit_count()

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a candidate’s understanding of bitwise operations like XOR.
question_mark
Check if the candidate can implement bit counting techniques like Brian Kernighan’s algorithm.
question_mark
Assess if the candidate can explain and optimize bit manipulation techniques for clarity and efficiency.

warning

常见陷阱

外企场景

error
Candidates may use inefficient methods such as converting integers to binary strings and counting differences, which is slower.
error
Failure to understand how to properly count set bits in the XOR result can lead to incorrect results.
error
Candidates may overlook optimizations such as Brian Kernighan’s algorithm and default to slower iterative methods.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the integers are represented in a different number of bits?
arrow_right_alt
How would you modify your approach for signed integers?
arrow_right_alt
Can you optimize further for large input ranges?

help

常见问题

外企场景

继续练习

#464 我能赢吗 #473 火柴拼正方形 #476 数字的补数