461. Hamming Distance

Problem Statement

link: LeetCode.cn LeetCode

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

Example:

Input: x = 1, y = 4 Output: 2

Input: x = 3, y = 1 Output: 1

Solution Approach

The algorithm computes the Hamming distance by using the XOR operator to find differing bits between the integers and then counts the number of set bits in the result.

Algorithm

1. XOR Operation: The algorithm uses the XOR operator (^) to identify differing bits between the two integers, producing a result where each bit is set to 1 if the corresponding bits of the input integers differ.
2. Count Set Bits: It counts the number of set bits (1s) in the XOR result using a bitwise AND operation (& 1) and bitwise right shift (»).
3. Efficient Calculation: The calculation is efficient as it processes a fixed number of bits (32 or 64, depending on the integer size) regardless of the integer values.

Complexity

time complexity: O(1) space complexity: O(1)

Implement

    class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        tmp = x ^ y  
        res = 0
        while tmp > 0:  
            res += tmp & 1
            tmp >>= 1
        return res
        

    
    

Twitter  facebook  Email