We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Hamming Distance

Number: 461

Difficulty: Easy

Paid? No

Companies: Microsoft, Google, Amazon, Meta

Problem Description

Given two integers x and y, determine the number of positions at which the corresponding bits are different, i.e., find the Hamming distance between the two integers.

Key Insights

  • The Hamming distance between two integers can be obtained by computing the XOR of x and y.
  • The XOR operation highlights the bits that differ between the two numbers.
  • Counting the number of set bits (1s) in the XOR result gives the required Hamming distance.
  • An efficient method to count set bits is to repeatedly clear the least significant bit set using bit manipulation (n = n & (n - 1)).

Space and Time Complexity

Time Complexity: O(1) (since the numbers are 32-bit, the operation takes constant time)
Space Complexity: O(1)

Solution

The solution involves computing the XOR of the two given integers. The resulting number will have bits set only at the positions where x and y differ. The next step is to count the number of 1s in this XOR result. This count directly represents the Hamming distance. We can count the set bits by iteratively removing the lowest set bit (using the operation n = n & (n - 1)) until the number becomes zero. This approach is efficient and leverages basic bit manipulation techniques.

Code Solutions

# Function to calculate Hamming distance between two integers.
def hammingDistance(x, y):
    # Compute XOR of x and y to highlight differing bits.
    xor_result = x ^ y
    count = 0
    # Count the number of set bits in xor_result.
    while xor_result:
        # Remove the lowest set bit.
        xor_result &= xor_result - 1
        count += 1
    return count

# Example usage:
print(hammingDistance(1, 4))  # Output: 2
← Back to All Questions