【鏈接】：461Hamming Distance 【描述】： 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. 【中文】：漢明距離是使用在數(shù)據(jù)傳輸差錯(cuò)控制編碼里面的，漢明距離是一個(gè)概念，它表示兩個(gè)（相同長度）字對應(yīng)位不同的數(shù)量，我們以d（x,y）表示兩個(gè)字x,y之間的漢明距離。對兩個(gè)字符串進(jìn)行異或運(yùn)算，并統(tǒng)計(jì)結(jié)果為1的個(gè)數(shù)，那么這個(gè)數(shù)就是漢明距離。 【思路】： 代碼：【1】第一個(gè)常見的思路就是把異或得到的數(shù)轉(zhuǎn)換為二進(jìn)制統(tǒng)計(jì)。 【2】第二個(gè)比較快一點(diǎn)的思路是用”與”操作，不斷清除n的二進(jìn)制表示中最右邊的1，同時(shí)累加計(jì)數(shù)器，直至n為0，這種方法速度比較快，其運(yùn)算次數(shù)與輸入n的大小無關(guān)，只與n中1的個(gè)數(shù)有關(guān)。如果n的二進(jìn)制表示中有M個(gè)1，那么這個(gè)方法只需要循環(huán)k次即可，所以其時(shí)間復(fù)雜度O(M)，代碼實(shí)現(xiàn)如下：
/***********************【LeetCode】461Hamming DistanceAuthor：herongweiTime:2017/2/7 10:52language：Chttp://blog.csdn.net/u013050857***********************/#PRagma comment(linker,"/STACK:102400000,102400000")#include <bits/stdc++.h>#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;typedef long long LL;const int maxn = 1e5+10;const int maxm = 55;const LL MOD = 999999997;int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};inline LL read(){ int c=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} return c*f;}int HammingDistance1(int x,int y){ int z=x^y; int sum=0; while(z){ z&=(z-1); sum++; } return sum;}int HammingDistance2(int x,int y){ int z=x^y; int sum=0; while(z){ if(z%2==1) sum++; z/=2; } return sum;}int main(){ //printf("%d/n",HammingDistance1(4,2)); return 0;}新聞熱點(diǎn)
疑難解答
