0461._Hamming_Distance.md

461. Hamming Distance

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/hamming-distance/description/

内容描述

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 < 231.

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.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

有wikipedia的page：

https://en.wikipedia.org/wiki/Hamming_distance

其实思路还是比较简单的

先用异或，再求hamming weight

For binary strings a and b the Hamming distance is equal to the number of ones (Hamming weight) in a XOR b.

beats 100%

一行无敌

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x^y).count('1')

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

不用count，用位运算更快，虽然在这里全部都是beats 100%

AC代码

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        dist = 0
        val = x ^ y

        while val:
            dist += 1
            val &= val - 1

        return dist