Hamming Distance

Problem Statement

The concept of Hamming distance is used to determine the difference between two integers at the binary level. Specifically, it measures the number of bit positions in which the two numbers differ. For this task, you are given two integers, x and y. The objective is to compute the Hamming distance between these two integers. This involves comparing their binary representations and counting the positions where the bits are not the same.

Examples

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

Approach and Intuition

Given the definition of the Hamming distance, we can deduce an approach to find the distance using the properties of binary numbers.

1. Convert to Binary and XOR Operation:

   • Convert the numbers to binary format.
   • Use the XOR bitwise operation between x and y. The XOR operation will return a binary number where bits are set to 1 wherever the two binary representations of x and y have differing bits.

2. Count the Set Bits:

   • After performing the XOR operation, count the number of bits that are set to 1 in the result. This count gives the Hamming distance since each 1 represents a position where x and y have different bits.

Examples

• Example 1:

  • Input: x = 1, y = 4
  • Binary Representation: 1 -> 0001, 4 -> 0100
  • XOR Result: (0001) XOR (0100) = 0101
  • The 1s in the XOR result are at two positions; therefore, the Hamming distance is 2.

• Example 2:

  • Input: x = 3, y = 1
  • Binary Representation: 3 -> 0011, 1 -> 0001
  • XOR Result: (0011) XOR (0001) = 0010
  • The 1 in the XOR result is at one position, making the Hamming distance 1.

Constraints

• The integers x and y will be non-negative and can go up to (2^31) - 1.

This implies that our approach needs to efficiently handle large numbers and should work uniformly across the possible range of values for x and y. Using bitwise operations like XOR ensures that our solution is both time-efficient and space-efficient, which is crucial given the constraints.

Solutions

class Solution {
  public int calculateHamming(int num1, int num2) {
    int resultXor = num1 ^ num2;
    int hammingDist = 0;
    while (resultXor != 0) {
      hammingDist += 1;
      resultXor = resultXor & (resultXor - 1);
    }
    return hammingDist;
  }
}