Problem statement

The Hamming distance between two integers is the number of bit positions at which they differ.

Given two non-negative integers x and y, return their Hamming distance.

Example 1

Input: x = 1, y = 4
Output: 2
Explanation: 0001 versus 0100 — two positions differ.

Example 2

Input: x = 3, y = 1
Output: 1

Example 3

Input: x = 0, y = 0
Output: 0

Constraints

• 0 <= x, y <= 2147483647

Hints for Hamming Distance

1. Hint 1

   XOR sets exactly the bits where the two numbers disagree.

2. Hint 2

   So the answer is the number of 1 bits in x ^ y.

3. Hint 3

   Count those with a shift loop or repeated v & (v - 1).

How to solve Hamming Distance

XOR marks the positions where the two numbers differ; count its set bits.

Approach

1. Compute x ^ y.
2. Return its popcount.

Why it works

A bit of the XOR is 1 exactly when the operands disagree there.

Complexity

• Time — O(1)
• Space — O(1)

Pitfalls

• Count with v & (v - 1) or a builtin popcount.

Reference solution

Python

def hammingDistance(x: int, y: int) -> int:
    return bin(x ^ y).count("1")

Java

public static int hammingDistance(int x, int y) {
    int v = x ^ y;
    int count = 0;
    while (v != 0) {
        v &= v - 1;
        count++;
    }
    return count;
}

C++

int hammingDistance(int x, int y) {
    unsigned int v = (unsigned int) (x ^ y);
    int count = 0;
    while (v) {
        v &= v - 1;
        count++;
    }
    return count;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More bit manipulation problems

• Convert Binary Number in a Linked List to Integer Easy
• Count Complete Tree Nodes Easy
• Sum of Root To Leaf Binary Numbers Easy
• Two Out of Three Easy
• Number of Bit Changes to Make Two Integers Equal Easy
• Find the XOR of Numbers Which Appear Twice Easy