Problem

In computer science, Hamming distance is used to quantify the difference between two binary strings. It is defined as the number of positions where the corresponding bits in the two strings are different. In this problem, given two integers, we are asked to calculate the Hamming distance between them. In other words, we have to determine how many bits in the binary representation of the two integers are different.

For instance, let's take the numbers 1 and 4. In the binary number system:

11 is represented as 0 0 0 1
24 is represented as 0 1 0 0

Clearly, there are 2 positions (the second position from the right, and the fourth position) where the corresponding bits are different. Therefore, the Hamming distance between 1 and 4 is 2.

Approach

The key to the solution is understanding how to compare individual bits of two integers. This can be achieved by using bitwise operations in the following way:

• We can use the bitwise OR operator (|) to keep comparing the bits until both numbers become 0.
• To compare the last bits of x and y, we use the bitwise AND operator (&) with 1 (since the binary representation of 1 is ...0001, which preserves the last bit of x and y and sets all other bits to 0), and then take the bitwise XOR of these results to determine if the last bits of x and y are the same or not. After each comparison, we increment our counter if the bits are different (i.e., their XOR is 1).
• We then right-shift both numbers (i.e., discard the last bit of both numbers and move the rest of the bits one position to the right), and repeat the process until both numbers become 0.

Following this approach ensures that we look at each bit of the two integers exactly once, resulting in an efficient solution to the problem.

Python Solution

1
2python
3class Solution:
4    def hammingDistance(self, x: int, y: int) -> int:
5        distance = 0
6        # keep shifting until both numbers become 0
7        while x or y:
8            # compare the last bit of x and y
9            distance += (x & 1) ^ (y & 1)
10            # right shift both numbers
11            x >>= 1
12            y >>= 1
13        return distance

Java Solution

1
2java
3class Solution {
4    public int hammingDistance(int x, int y) {
5        int distance = 0;
6        while (x != 0 || y != 0) {
7            distance += (x & 1) ^ (y & 1);
8            x >>= 1;
9            y >>= 1;
10        }
11        return distance;
12    }
13}

JavaScript Solution

1
2javascript
3class Solution {
4 hammingDistance(x, y) {
5    let distance = 0;
6    while (x > 0 || y > 0) {
7        distance += (x & 1) ^ (y & 1);
8        x >>= 1;
9        y >>= 1;
10    }
11    return distance;
12  }
13}

C++ Solution

1
2c++
3class Solution {
4public:
5    int hammingDistance(int x, int y) {
6        int distance = 0;
7        while (x > 0 || y > 0) {
8            distance += (x & 1) ^ (y & 1);
9            x >>= 1;
10            y >>= 1;
11        }
12        return distance;
13    }
14};

C# Solution

1
2csharp
3public class Solution {
4    public int HammingDistance(int x, int y) {
5        int distance = 0;
6        while (x > 0 || y > 0) {
7            distance += (x & 1) ^ (y & 1);
8            x >>= 1;
9            y >>= 1;
10        }
11        return distance;
12    }
13}

The above solutions all follow the described approach and are able to calculate the Hamming distance in a very efficient manner. Every operation used (bitwise AND, bitwise XOR, bitwise shift and addition) are all constant-time operations, making the overall time complexity of the solution O(1).## Testing

After implementing the solution, you should always test your code with various test cases to ensure it meets the problem's requirements.

In Python:

1
2python
3s = Solution()
4print(s.hammingDistance(1, 4))  # Output: 2
5print(s.hammingDistance(3, 1))  # Output: 1
6print(s.hammingDistance(7, 0))  # Output: 3

In Java:

1
2java
3Solution s = new Solution();
4System.out.println(s.hammingDistance(1, 4));  // Output: 2
5System.out.println(s.hammingDistance(3, 1));  // Output: 1
6System.out.println(s.hammingDistance(7, 0));  // Output: 3

In JavaScript:

1
2javascript
3const s = new Solution();
4console.log(s.hammingDistance(1, 4));  // Output: 2
5console.log(s.hammingDistance(3, 1));  // Output: 1
6console.log(s.hammingDistance(7, 0));  // Output: 3

In C++:

1
2c++
3Solution s;
4cout << s.hammingDistance(1, 4)  << endl; // Output: 2
5cout << s.hammingDistance(3, 1)  << endl; // Output: 1
6cout << s.hammingDistance(7, 0)  << endl; // Output: 3

In C#:

1
2csharp
3Solution s = new Solution();
4Console.WriteLine(s.HammingDistance(1, 4));  // Output: 2
5Console.WriteLine(s.HammingDistance(3, 1));  // Output: 1
6Console.WriteLine(s.HammingDistance(7, 0));  // Output: 3

The outputs match the expected results, indicating our algorithm is functioning as expected.

Conclusion

The Hamming distance is a common concept in computer science that measures the difference between two binary strings. In this article, we presented an efficient way to calculate the Hamming distance for two integers by using bitwise operations. We provided implementations of this approach in Python, Java, JavaScript, C++, and C#, each of which has a constant time complexity. Therefore, this solution can be used to solve problems that require calculating the Hamming distance in large datasets or in real-time systems.