兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對應(yīng)二進(jìn)制位不同的位置的數(shù)目渔伯。
給出兩個(gè)整數(shù) x 和 y惭等，計(jì)算它們之間的漢明距離掉冶。
注意：
0 ≤ x, y < 231.
示例:
輸入: x = 1, y = 4
輸出: 2
解釋:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭頭指出了對應(yīng)二進(jìn)制位不同的位置路幸。
思路：
x和y按位異或楼雹，得到所有不同的位
模二取余模孩，余數(shù)累加
具體代碼：
class Solution {
public:
int hammingDistance(int x, int y) {
int z = x ^ y; //按位異或
int res = 0; //結(jié)果
while(z){ //遍歷z每一位
if(z % 2){ //假設(shè)z最低位為1
res++; //結(jié)果++
}
z /= 2; //z抹去最后一位
}
return res; //返回結(jié)果
}
};
代碼借鑒：
百度發(fā)現(xiàn)了一個(gè)新穎的寫法
參考資料《leetCode:461 漢明距離》
class Solution {
public int hammingDistance(int x, int y) {
int sum = x ^ y;
int count;
for(count = 0; sum > 0; count++){
sum &= (sum - 1);
}
return count;
}
}
其中關(guān)鍵一句是 sum &= (sum - 1)
這句話的作用是，刪除sum從右起第一個(gè)1
證明：
加入sum形如xxxx1,
則sum - 1形如xxxx0
做與運(yùn)算后贮缅，結(jié)果為xxxx0榨咐，末尾的1被刪去了
假設(shè)sum形如xxxx100...00
則sum - 1形如xxxx011...11
做與運(yùn)算后，結(jié)果為xxxx000...00谴供，可以觀察到块茁，末尾的1被刪去了
這個(gè)方法執(zhí)行for循環(huán)，效果也很不錯(cuò)桂肌，也不用添加額外的if判斷了
