# LeetCode 461: Hamming Distance

## Problem Restatement

We are given two integers `x` and `y`.

We need to return the Hamming distance between them.

For two integers, the Hamming distance is the number of bit positions where their binary representations are different. The official problem asks us to return the Hamming distance between two integers `x` and `y`.

For example:

```python
x = 1
y = 4
```

Their binary forms are:

```python
1 = 0001
4 = 0100
```

They differ in two positions:

```python
0001
0100
 ^ ^
```

So the answer is:

```python
2
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `x` and `y` |
| Output | Number of bit positions where `x` and `y` differ |
| Constraint | `0 <= x, y <= 2^31 - 1` |

Function shape:

```python
def hammingDistance(x: int, y: int) -> int:
    ...
```

## Examples

Example 1:

```python
x = 1
y = 4
```

Binary:

```python
1 = 0001
4 = 0100
```

Different positions:

```python
0001
0100
 ^ ^
```

Answer:

```python
2
```

Example 2:

```python
x = 3
y = 1
```

Binary:

```python
3 = 0011
1 = 0001
```

Only one bit differs:

```python
0011
0001
  ^
```

Answer:

```python
1
```

Example 3:

```python
x = 0
y = 0
```

Both numbers have the same binary representation.

Answer:

```python
0
```

## First Thought: Compare Bits One by One

A direct approach is to inspect every bit position.

Since the constraints fit inside 31 bits, we can check bits from `0` to `30`.

For each bit position, extract the bit from `x` and `y`.

If they differ, increment the answer.

```python
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        distance = 0

        for bit in range(31):
            bit_x = (x >> bit) & 1
            bit_y = (y >> bit) & 1

            if bit_x != bit_y:
                distance += 1

        return distance
```

This works because the Hamming distance is exactly the count of positions where the two bits differ.

## Problem With Manual Bit Comparison

The bit-by-bit approach is already efficient because there are only 31 relevant bits.

But the code is more verbose than needed.

There is a bit operation that directly marks all different positions: XOR.

## Key Insight

XOR has the exact behavior we need.

For each bit:

| Bit in `x` | Bit in `y` | `x ^ y` bit |
|---:|---:|---:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

So `x ^ y` has `1` exactly at positions where `x` and `y` differ.

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

For example:

```python
x = 1      # 0001
y = 4      # 0100
x ^ y = 5  # 0101
```

The result `0101` has two `1` bits.

So the Hamming distance is:

```python
2
```

## Algorithm

Compute:

```python
diff = x ^ y
```

Then count the number of set bits in `diff`.

In Python, this can be done directly:

```python
diff.bit_count()
```

Return that count.

## Correctness

For every bit position, XOR returns `1` exactly when the two input bits are different.

Therefore, after computing:

```python
diff = x ^ y
```

the number of `1` bits in `diff` equals the number of bit positions where `x` and `y` differ.

The Hamming distance is defined as exactly that count.

So returning the number of set bits in `x ^ y` gives the correct answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | Inputs fit in a fixed integer width |
| Space | `O(1)` | Only one extra integer is used |

For arbitrary-size integers, the time depends on the number of machine words used to store the integers.

## Implementation

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

## Code Explanation

The expression:

```python
x ^ y
```

creates a number whose `1` bits mark the positions where `x` and `y` are different.

Then:

```python
.bit_count()
```

counts how many `1` bits that number has.

That count is the Hamming distance.

## Alternative Implementation Without `bit_count`

Some languages or older Python versions may not have `bit_count`.

We can count set bits manually using Brian Kernighan's trick.

```python
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        diff = x ^ y
        distance = 0

        while diff:
            diff &= diff - 1
            distance += 1

        return distance
```

The operation:

```python
diff &= diff - 1
```

removes the lowest set bit from `diff`.

So the loop runs once per `1` bit.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.hammingDistance(1, 4) == 2
    assert s.hammingDistance(3, 1) == 1
    assert s.hammingDistance(0, 0) == 0
    assert s.hammingDistance(0, 7) == 3
    assert s.hammingDistance(15, 0) == 4
    assert s.hammingDistance(8, 8) == 0
    assert s.hammingDistance(2**31 - 1, 0) == 31

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1, 4` | Standard example |
| `3, 1` | One differing bit |
| `0, 0` | Same numbers |
| `0, 7` | Count all set bits in one number |
| `15, 0` | Multiple low bits differ |
| `8, 8` | Equal non-zero numbers |
| `2^31 - 1, 0` | Maximum 31-bit all-ones case |