# Hamming Distance
**Difficulty:** EASY
[External](https://leetcode.com/problems/hamming-distance)
Canonical: https://scaleengineer.com/dsa/problems/hamming-distance
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
The [Hamming distance](https://en.wikipedia.org/wiki/Hamming%5Fdistance) 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)
       ↑   ↑
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 <= 231 - 1`

**Note:** This question is the same as [ 2220: Minimum Bit Flips to Convert Number.](https://leetcode.com/problems/minimum-bit-flips-to-convert-number/description/)

# Approaches
## Brute Force using String Conversion
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.
**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.
**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.
### Explanation
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.

1.  Convert both integers `x` and `y` to their binary string representations.
2.  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.
3.  Once they have the same length, we can iterate through them and count the positions where the characters (bits) do not match.

```java
class Solution {
    public int hammingDistance(int x, int y) {
        String xStr = Integer.toBinaryString(x);
        String yStr = Integer.toBinaryString(y);

        int lenX = xStr.length();
        int lenY = yStr.length();
        int maxLen = Math.max(lenX, lenY);

        // Pad with leading zeros
        while (xStr.length() < maxLen) {
            xStr = "0" + xStr;
        }
        while (yStr.length() < maxLen) {
            yStr = "0" + yStr;
        }

        int distance = 0;
        for (int i = 0; i < maxLen; i++) {
            if (xStr.charAt(i) != yStr.charAt(i)) {
                distance++;
            }
        }
        return distance;
    }
}
```
### 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`.

## Bit-by-bit Comparison
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int hammingDistance(int x, int y) {
        int distance = 0;
        for (int i = 0; i < 32; i++) {
            // Extract the i-th bit of x and y
            int bitX = (x >> i) & 1;
            int bitY = (y >> i) & 1;
            if (bitX != bitY) {
                distance++;
            }
        }
        return distance;
    }
}
```
### 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.

## Bit Manipulation with XOR and Right Shift
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.
**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.
**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.
### Explanation
The key insight is that the Hamming distance is the number of set bits in the XOR of the two numbers.

1.  First, calculate `xor_result = x ^ y`. This single operation effectively marks all differing bit positions with a '1'.
2.  Now, we need to count the set bits in `xor_result`.
3.  We can do this by repeatedly checking the least significant bit (LSB) and then right-shifting the number until it becomes zero.
4.  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.

```java
class Solution {
    public int hammingDistance(int x, int y) {
        int xor_result = x ^ y;
        int distance = 0;
        while (xor_result != 0) {
            distance += (xor_result & 1);
            // Use unsigned right shift >>> if dealing with negative numbers,
            // but constraints are non-negative. >> is fine here.
            xor_result = xor_result >> 1;
        }
        return distance;
    }
}
```
### 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`.

## Optimized Bit Counting with Brian Kernighan's Algorithm
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`.
**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).
**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.
### Explanation
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.

1.  As before, calculate `xor_result = x ^ y`.
2.  Initialize a `distance` counter to 0.
3.  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.
4.  The loop terminates when `xor_result` becomes 0, meaning all set bits have been removed.

```java
class Solution {
    public int hammingDistance(int x, int y) {
        int xor_result = x ^ y;
        int distance = 0;
        while (xor_result != 0) {
            // This operation removes the rightmost set bit
            xor_result = xor_result & (xor_result - 1);
            distance++;
        }
        return distance;
    }
}
```
### 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`.

## Using Built-in Population Count Function
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.
**Time:** O(1). The operation is typically a single CPU instruction, making it constant time and extremely fast. · **Space:** O(1).
**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.
### Explanation
This approach leverages the standard library for maximum efficiency and conciseness. The logic is extremely simple.

1.  First, calculate the bitwise XOR of the two numbers: `xor_result = x ^ y`.
2.  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.

```java
class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}
```
### Algorithm
- Compute `xor_result = x ^ y`.
- Return the result of `Integer.bitCount(xor_result)`.

# Solutions
### Java

```java
class Solution {
public
  int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }
}

```

### JavaScript

```javascript
/** * @param {number} x * @param {number} y * @return {number} */ var hammingDistance =
  function (x, y) {
    x ^= y;
    let ans = 0;
    while (x) {
      x -= x & -x;
      ++ans;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); }
};

```

### Python

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

```