Hamming Distance - Leetcode Solution

The Hamming Distance problem on LeetCode involves finding the Hamming distance between two integers. The Hamming distance between two integers is defined as the number of positions at which the corresponding bits are different.

For example, the Hamming distance between 1 (0b0001) and 4 (0b0100) is 2, since the 2nd and 4th bits are different.

The input consists of two integers, x and y, and the output is the Hamming distance between them.

One possible solution to this problem in Python is as follows:

def hammingDistance(x: int, y: int) -> int:
    # XOR the two integers to get their bitwise difference
    xor = x ^ y
    
    # Initialize the Hamming distance to be 0
    distance = 0
    
    # Count the number of set bits (i.e., 1's) in the XOR result
    while xor > 0:
        if xor & 1 == 1:
            distance += 1
        xor >>= 1
    
    return distance

First, we compute the bitwise XOR of the two input integers. This yields an integer whose binary representation has a 1 in each position where the corresponding bits of x and y are different, and a 0 where they are the same.

Next, we initialize a variable called distance to 0. This variable will be used to count the number of positions where the XOR result has a 1.

Then, we loop through the binary representation of the XOR result from right to left (i.e., from the least significant bit to the most significant bit). At each iteration, we check whether the current bit is a 1 using the bitwise AND operator with the value 1. If it is, we increment the distance counter. Finally, we right-shift the XOR result by one bit, effectively moving to the next (more significant) bit in the binary representation.

After the loop finishes, the distance counter contains the Hamming distance between x and y, which we return as the function output.

Overall, the time complexity of this solution is O(log(max(x,y))), since we need to loop through the binary representation of the XOR result, which has a maximum length of log base 2 of the larger of the two input integers. The space complexity is O(1), since we only use a constant amount of extra space to store the distance counter and the loop variables.

1