Hamming Distance XOR (Golang) bit operation


  • 2
    W

    Question     461. Hamming Distance


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

    Given two integers x and y, calculate the Hamming distance.

    Note:
    0 ≤ x, y < 2^31.

    Example:

    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.

    Solution


    With golang, bit operation

    1、get the different bits with XOR operations

    1 (0 0 0 1)
    xor
    4 (0 1 0 0)
    ==>
    (0101)

    now, only need count the number of '1' bits

    2、count

    first, we need a bitmask like (0 0 0 1), and left shift it to compare each bit of your xor result (in the previous step), if "bitmask AND xor" is not 0, counter increase 1

    then, stop left shift when bitmask overflowed (the value of int is a negative number, unsigned int is 0, so, just check bitmask is more than 0 or not).

    Example:

    (1 0 1 0)
    AND
    (0 0 0 1)
    ==>
    0
     
    left shift
     
    (1 0 1 0)
    AND
    (0 0 1 0)
    ==>
    is not 0, counter++
     
    left shift
     
    (1 0 1 0)
    AND
    (0 1 0 0)
    ==>
    0
    ......
     
    bitmask overflowed : (0 0 0 0) or (1 1 1 1)
    stop
     
    result : 2

    Code:

    func hammingDistance(x int, y int) int {
    
        count := 0
        
        xor := x ^ y  /* get xor bits */
    
        /* when overflow, exit loop */
        for bitMask := 1; bitMask > 0; bitMask <<= 1 {
            if bitMask & xor != 0 { /* find bit 1 */
               count++ 
            }
        }
        
        return count
    }
    

    Complexity Analysis:

    • Time complexity : O(1).
      The times of for loop is const, so the time complexity is O(1).

    • Space complexity : O(1).
      We only need constant memory to store 3 local variables, so the space complexity is O(1).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.