Leetcode详详解

461. Hamming Distance

2018-11-30  本文已影响0人  Chrisbupt

Leetcode Day 2

题目:
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.

tips :
这道题的目的就是要求两个数字之间的汉明距离。两个数字之间的汉明距离是两个数字二进制下对应位不同的个数。
思路:
将两个数字的二进制进行异或运算,不同的位数得到1,将1累加起来就是两个数字的汉明距离。

⊕是XOR运算:异或运算就是如果两个数字(0或者1)相同,则输出为0; 如果两个数字(0或者1)不相同,就输出为a

  1. python

# 先将x,y表示为二进制数, 用函数bin
# 也可以通过对该数字除以2 i次,得到的余数即为第i 位(从右开始)
 def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x^y).count('1')
 //
ans = 0
while x or y:
  ans += (x % 2) ^ (y % 2)
  x /= 2
  y /= 2
return ans
//
  1. C++
    将x和y异或操作之后计算n其中二进制中1的个数,其计算的方法是通过自身n和自身减一n-1的二进制数逐位相与&,然后减一之后继续循环直至为0,这样也就将其二进制中1的个数计算出来
class Solution{
public:
      int hammingDistance(int x, int y){
            int dist = 0, n =x^y;
            while(n){  // 
                ++dist;
                n &= n-1;
}

}


}
上一篇下一篇

猜你喜欢

热点阅读