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 < 2³¹.

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 :
這道題的目的就是要求兩個(gè)數(shù)字之間的漢明距離。兩個(gè)數(shù)字之間的漢明距離是兩個(gè)數(shù)字二進(jìn)制下對(duì)應(yīng)位不同的個(gè)數(shù)。
思路:
將兩個(gè)數(shù)字的二進(jìn)制進(jìn)行異或運(yùn)算，不同的位數(shù)得到1，將1累加起來就是兩個(gè)數(shù)字的漢明距離。

⊕是XOR運(yùn)算：異或運(yùn)算就是如果兩個(gè)數(shù)字（0或者1）相同,則輸出為0; 如果兩個(gè)數(shù)字（0或者1）不相同,就輸出為a

• a⊕0=a
• a⊕a=0
• a⊕b⊕a= (a⊕a)⊕b=b

1. python

# 先將x,y表示為二進(jìn)制數(shù)， 用函數(shù)bin
# 也可以通過對(duì)該數(shù)字除以2 i次，得到的余數(shù)即為第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
//

2. C++
   將x和y異或操作之后計(jì)算n其中二進(jìn)制中1的個(gè)數(shù)，其計(jì)算的方法是通過自身n和自身減一的二進(jìn)制數(shù)逐位相與，然后減一之后繼續(xù)循環(huán)直至為0，這樣也就將其二進(jìn)制中1的個(gè)數(shù)計(jì)算出來

class Solution{
public:
      int hammingDistance(int x, int y){
            int dist = 0, n =x^y;
            while(n){  // 
                ++dist;
                n &= n-1;
}

}


}