Golang concise solution with explanation


  • 0

    First, by calculating x ^ y, we can get the num whose bit representations shows 1 only when the bits in x and y are different. That is to say, our task is count a number of 1 in x ^ y.

    How we can check the count of digits 1 of some bit representation?
    Of course we can check whether each digit is 1 while shifting to right one by one. But there is a faster solution for this problem. I saw the following technique in Elements in programming inteview.

    let's say a bit representation is X = 1001000.
    Then consider X - 1 = 1000111
    Then try calculate X & X-1 = 1000000.

    What happened here? We can reset the most right 1 occurrence from X without checking rightmost three 0 digits! In this way, we can speed up the iteration to O(n) while n is the occurrence of 1 in X, not the length of digit of X. (Of course, the worst case time complexity is the same but practically this is much more efficient)

    func hammingDistance(x int, y int) int {
    	xor := x ^ y
    
    	res := 0
    	for xor != 0 {
    		xor = xor & (xor - 1)
    		res++
    	}
    	return res
    }
    

Log in to reply
 

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