Hamming Distance

Easy

#0448Time: O(k), where k is the number of bits in the larger number. String conversions, padding, and iteration all take time proportional to the number of bits. For 32-bit integers, this is effectively O(1) but with a high constant factor.Space: O(k), where k is the number of bits in the larger number (at most 32). This space is used to store the binary string representations.

Patterns

Bit Manipulation

Prompt

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

Example 1:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       &uarr;   &uarr;
The above arrows point to positions where the corresponding bits are different.

Example 2:

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

Constraints:

0 <= x, y <= 2³¹ - 1

Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.

Approaches

5 approaches with complexity analysis and trade-offs.

This approach converts both integers into their binary string representations. It then compares these strings character by character to count the differences. To handle numbers of different bit lengths, the shorter string is padded with leading zeros to match the length of the longer one.

Algorithm

Convert x to a binary string using Integer.toBinaryString(x).
Convert y to a binary string using Integer.toBinaryString(y).
Determine the maximum length of the two strings.
Pad the shorter string with leading '0's so both strings have the same length.
Iterate from 0 to length - 1.
In each iteration, compare the characters at the current index. If they are different, increment a distance counter.
Return the final distance.

Walkthrough

This method is straightforward but less performant. It relies on standard library functions to convert numbers to strings and then performs a character-by-character comparison.

Convert both integers x and y to their binary string representations.
Since the binary strings can have different lengths (e.g., Integer.toBinaryString(1) is "1" and Integer.toBinaryString(4) is "100"), we need to make them equal in length by padding the shorter string with leading zeros.
Once they have the same length, we can iterate through them and count the positions where the characters (bits) do not match.

1class Solution {2    public int hammingDistance(int x, int y) {3        String xStr = Integer.toBinaryString(x);4        String yStr = Integer.toBinaryString(y);5 6        int lenX = xStr.length();7        int lenY = yStr.length();8        int maxLen = Math.max(lenX, lenY);9 10        // Pad with leading zeros11        while (xStr.length() < maxLen) {12            xStr = "0" + xStr;13        }14        while (yStr.length() < maxLen) {15            yStr = "0" + yStr;16        }17 18        int distance = 0;19        for (int i = 0; i < maxLen; i++) {20            if (xStr.charAt(i) != yStr.charAt(i)) {21                distance++;22            }23        }24        return distance;25    }26}

Complexity

Time

O(k), where k is the number of bits in the larger number. String conversions, padding, and iteration all take time proportional to the number of bits. For 32-bit integers, this is effectively O(1) but with a high constant factor.

Space

O(k), where k is the number of bits in the larger number (at most 32). This space is used to store the binary string representations.

Trade-offs

Pros

Conceptually simple and easy to understand for those less familiar with bitwise operations.

Cons

Inefficient due to the overhead of string creation, manipulation, and memory allocation.
Slower than direct bitwise manipulation.
Requires extra space to store the string representations.

This approach iterates through each bit of the two numbers, from the least significant bit to the most significant bit. In each iteration, it uses bitwise operations to extract and compare the corresponding bits of x and y and increments a counter if they differ.

Algorithm

Initialize distance = 0.
Loop 32 times, for each bit position i from 0 to 31.
Extract the i-th bit of x and y using right shift and AND operations: (x >> i) & 1 and (y >> i) & 1.
If the bits are different, increment distance.
Return distance after the loop.

Walkthrough

Instead of converting to strings, we can work directly with the integer representations. Since integers are stored as a fixed number of bits (32 in this case), we can loop 32 times and check each bit position individually.

We use a loop that runs from i = 0 to 31.
In each iteration, we isolate the i-th bit of both x and y. This is done by right-shifting the number by i positions, which moves the i-th bit to the least significant position, and then performing a bitwise AND with 1.
We compare these two extracted bits. If they are not equal, we increment our distance counter.
After checking all 32 bits, the counter holds the Hamming distance.

1class Solution {2    public int hammingDistance(int x, int y) {3        int distance = 0;4        for (int i = 0; i < 32; i++) {5            // Extract the i-th bit of x and y6            int bitX = (x >> i) & 1;7            int bitY = (y >> i) & 1;8            if (bitX != bitY) {9                distance++;10            }11        }12        return distance;13    }14}

Complexity

Time

O(k), where k is the number of bits in an integer (fixed at 32). The loop runs a constant number of times. Therefore, the complexity is O(1).

Space

O(1), as we only use a few variables for the counter and loop index.

Trade-offs

Pros

More efficient than the string-based approach as it avoids string overhead.
Constant time and space complexity.

Cons

It always performs a fixed number of iterations (32), regardless of the actual values of x and y, which might be inefficient for small numbers.

A more elegant bit manipulation approach first computes the bitwise XOR of x and y. The XOR operation x ^ y results in a number where a bit is set to 1 if and only if the corresponding bits in x and y were different. The problem then reduces to counting the number of set bits (1s) in the result of the XOR operation. This is also known as calculating the population count or Hamming weight.

Algorithm

Compute xor_result = x ^ y.
Initialize distance = 0.
While xor_result is not zero:
- Add (xor_result & 1) to distance.
- Right shift xor_result by 1 (xor_result = xor_result >> 1).
Return distance.

Walkthrough

The key insight is that the Hamming distance is the number of set bits in the XOR of the two numbers.

First, calculate xor_result = x ^ y. This single operation effectively marks all differing bit positions with a '1'.
Now, we need to count the set bits in xor_result.
We can do this by repeatedly checking the least significant bit (LSB) and then right-shifting the number until it becomes zero.
In a loop that continues as long as xor_result > 0:
- Check if the LSB is 1 using (xor_result & 1) == 1. If it is, increment distance.
- Right-shift xor_result by one position (xor_result = xor_result >> 1) to process the next bit.

1class Solution {2    public int hammingDistance(int x, int y) {3        int xor_result = x ^ y;4        int distance = 0;5        while (xor_result != 0) {6            distance += (xor_result & 1);7            // Use unsigned right shift >>> if dealing with negative numbers,8            // but constraints are non-negative. >> is fine here.9            xor_result = xor_result >> 1;10        }11        return distance;12    }13}

Complexity

Time

O(k), where k is the number of bits in the integer (32). The loop runs up to k times, depending on the position of the most significant set bit in `x ^ y`. For a fixed integer size, this is O(1).

Space

O(1), as only a few variables are used.

Trade-offs

Pros

More concise and often slightly faster in practice than direct bit-by-bit comparison of two numbers.
The number of iterations depends on the position of the highest set bit, not always 32.

Cons

The loop still iterates over all bits up to the most significant '1', including the '0's in between, which is less efficient than algorithms that only visit set bits.

This is a clever optimization for counting set bits, often known as Brian Kernighan's algorithm. Instead of shifting through all bits, this algorithm repeatedly eliminates the rightmost set bit. The number of times this operation can be performed is exactly equal to the number of set bits. The key operation is n & (n - 1), which unsets the rightmost '1' bit of n.

Algorithm

Compute xor_result = x ^ y.
Initialize distance = 0.
While xor_result is not zero:
- Increment distance.
- Update xor_result to xor_result & (xor_result - 1).
Return distance.

Walkthrough

This approach improves upon the previous one by reducing the number of loop iterations. The number of iterations will be exactly equal to the number of set bits, which is the Hamming distance we are looking for.

As before, calculate xor_result = x ^ y.
Initialize a distance counter to 0.
In a loop that continues as long as xor_result > 0:
- In each iteration, we know there is at least one set bit. We increment the distance counter.
- Then, we turn off the rightmost set bit using the operation: xor_result = xor_result & (xor_result - 1). For example, if xor_result is 12 (binary 1100), xor_result - 1 is 11 (binary 1011). 1100 & 1011 is 1000 (binary 8). The rightmost '1' has been turned off.
The loop terminates when xor_result becomes 0, meaning all set bits have been removed.

1class Solution {2    public int hammingDistance(int x, int y) {3        int xor_result = x ^ y;4        int distance = 0;5        while (xor_result != 0) {6            // This operation removes the rightmost set bit7            xor_result = xor_result & (xor_result - 1);8            distance++;9        }10        return distance;11    }12}

Complexity

Time

O(m), where m is the number of set bits in `x ^ y` (i.e., the Hamming distance). This is more efficient because the number of loop iterations is not tied to the total number of bits, but to the number of differing bits. In the worst case, m can be k (32), but on average, it's much better.

Space

O(1).

Trade-offs

Pros

Highly efficient. The number of operations is proportional to the Hamming distance itself, not the total number of bits.
Outperforms other manual bit-counting methods on average.

Cons

The logic n & (n - 1) might be less intuitive for beginners compared to simpler bit-shifting.

Most modern programming languages and processors provide a highly optimized built-in function to count the number of set bits in an integer (population count). This is almost always the fastest and most concise way to solve the problem.

Algorithm

Compute xor_result = x ^ y.
Return the result of Integer.bitCount(xor_result).

Walkthrough

This approach leverages the standard library for maximum efficiency and conciseness. The logic is extremely simple.

First, calculate the bitwise XOR of the two numbers: xor_result = x ^ y.
Then, use the language's built-in function to count the set bits in xor_result. In Java, this function is Integer.bitCount().

This function is often mapped to a single, fast machine instruction (like POPCNT on x86 processors), making it extremely efficient.

1class Solution {2    public int hammingDistance(int x, int y) {3        return Integer.bitCount(x ^ y);4    }5}

Complexity

Time

O(1). The operation is typically a single CPU instruction, making it constant time and extremely fast.

Space

O(1).

Trade-offs

Pros

The most efficient and concise solution.
It's readable and leverages hardware optimizations.

Cons

Relies on a built-in library function, which might not be allowed in some interview settings that want you to implement the logic from scratch.

Solutions

Solution

1class Solution {2public3  int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }4}

1/** * @param {number} x * @param {number} y * @return {number} */ var hammingDistance =2  function (x, y) {3    x ^= y;4    let ans = 0;5    while (x) {6      x -= x & -x;7      ++ans;8    }9    return ans;10  };

1class Solution {2public:3  int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); }4};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }4}

1/** * @param {number} x * @param {number} y * @return {number} */ var hammingDistance =2  function (x, y) {3    x ^= y;4    let ans = 0;5    while (x) {6      x -= x & -x;7      ++ans;8    }9    return ans;10  };

1class Solution {2public:3  int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); }4};

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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.