LeetCode 461: Hamming Distance (XOR + Set Bit Counting)

2026-04-06 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 461Bit ManipulationXORBit Count

Today we solve LeetCode 461 - Hamming Distance.

Source: https://leetcode.com/problems/hamming-distance/

LeetCode 461 XOR bits and count ones diagram

English

Problem Summary

Given two integers x and y, return how many bit positions are different between them.

Key Insight

x ^ y keeps exactly the differing bit positions as 1. So the answer is just the number of set bits in x ^ y.

Algorithm

1) Compute diff = x ^ y.
2) Count how many 1s are in diff.
3) Return that count.

Complexity Analysis

Time: O(k), where k is the number of bits (at most 31 for this problem range).
Space: O(1).

Common Pitfalls

- Comparing decimal digits instead of binary bits.
- Forgetting XOR and trying manual per-bit alignment with strings.
- Using signed-shift loops carelessly in languages where right shift keeps sign bits.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int hammingDistance(int x, int y) {
        int diff = x ^ y;
        int count = 0;
        while (diff != 0) {
            count += (diff & 1);
            diff >>>= 1;
        }
        return count;
    }
}

func hammingDistance(x int, y int) int {
    diff := x ^ y
    count := 0
    for diff != 0 {
        count += diff & 1
        diff >>= 1
    }
    return count
}

class Solution {
public:
    int hammingDistance(int x, int y) {
        int diff = x ^ y;
        int count = 0;
        while (diff != 0) {
            count += (diff & 1);
            diff >>= 1;
        }
        return count;
    }
};

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

var hammingDistance = function(x, y) {
  let diff = x ^ y;
  let count = 0;
  while (diff !== 0) {
    count += (diff & 1);
    diff >>>= 1;
  }
  return count;
};

中文

题目概述

给定两个整数 x 和 y，返回它们在二进制表示中不同位的个数。

核心思路

对两个数做异或：x ^ y。凡是不同的位会变成 1，所以答案就是这个结果里 1 的数量。

算法步骤

1）计算 diff = x ^ y。
2）循环统计 diff 的最低位是否为 1。
3）右移直到 diff 为 0，返回计数。

复杂度分析

时间复杂度：O(k)，k 为位数（本题范围内最多 31 位）。
空间复杂度：O(1)。

常见陷阱

- 把题目误解成十进制位比较。
- 不用 XOR，改用字符串对齐导致实现冗长。
- 在不同语言中混用有符号右移和无符号右移，导致边界行为不一致。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int hammingDistance(int x, int y) {
        int diff = x ^ y;
        int count = 0;
        while (diff != 0) {
            count += (diff & 1);
            diff >>>= 1;
        }
        return count;
    }
}

func hammingDistance(x int, y int) int {
    diff := x ^ y
    count := 0
    for diff != 0 {
        count += diff & 1
        diff >>= 1
    }
    return count
}

class Solution {
public:
    int hammingDistance(int x, int y) {
        int diff = x ^ y;
        int count = 0;
        while (diff != 0) {
            count += (diff & 1);
            diff >>= 1;
        }
        return count;
    }
};

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

var hammingDistance = function(x, y) {
  let diff = x ^ y;
  let count = 0;
  while (diff !== 0) {
    count += (diff & 1);
    diff >>>= 1;
  }
  return count;
};