7/13 每日一題(漢明距離,計算二進制中有幾個元素不同)

 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 1:

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.

Example 2:

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

 

Constraints:

• 0 <= x, y <= 231 - 1

class Solution:

    def hammingDistance(self, x: int, y: int) -> int:

        two_x=bin(x)[2:]

        two_y=bin(y)[2:]

        max_len=max(len(two_x),len(two_y)) #取最長

        i=0

        diff=0

        if len(two_x) > len(two_y):

            comp_y=two_y.zfill(max_len)

            while i < max_len:

                if two_x[i] != comp_y[i]:

                    diff +=1

                i+=1

            return diff

        elif len(two_x) < len(two_y):

            comp_x=two_x.zfill(max_len)

            while i < max_len:

                if two_y[i] != comp_x[i]:

                    diff +=1

                i+=1

            return diff

       

        else:

            while i < max_len:

                if two_x[i] != two_y[i]:

                    diff +=1

                i+=1

            return diff

-----參考解答

Intuition

Approach

Complexity

• Time complexity:

• Space complexity:

Code

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x^y)[2:].count("1")




令

x=5 >>0b0101

y=1 >>0b0001

使用^ 互斥 相同的會變成0 不同的變成1 所以只需要計算多少個1就是幾個不同

x^y=4 >>0b0100