Hamming Distance bit trick solution (no if/switch blocks used)


  • 0
    L

    I assume that the & operator represents bitwise AND operation and the - operator represents the negation operator (i.e. -5 is negation of 5).

    In order to get the last set bit (i.e. a 1 bit) in a base 2 number x, we use x & -x

    Hence x -= x & -x will remove the last set bit from x.

    So, all we need to do is to do bitwise XOR of the given numbers a and b and store their result in a separate variable c so that we know which bits they differ in.

    Now we run the following:

    while c > 0
    do
      c -= c & -c
      ans++
    done
    
    return ans
    

    We are done!

    Asuming complexity of bitwise operations is O(1), Complexity of this algorithm is O(k) where k is the number of set bits in the XOR of the given number.


Log in to reply
 

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