【鏈接】：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. 【中文】：漢明距離是使用在數據傳輸差錯控制編碼里面的，漢明距離是一個概念，它表示兩個（相同長度）字對應位不同的數量，我們以d（x,y）表示兩個字x,y之間的漢明距離。對兩個字符串進行異或運算，并統計結果為1的個數，那么這個數就是漢明距離。 【思路】： 代碼：【1】第一個常見的思路就是把異或得到的數轉換為二進制統計。 【2】第二個比較快一點的思路是用”與”操作，不斷清除n的二進制表示中最右邊的1，同時累加計數器，直至n為0，這種方法速度比較快，其運算次數與輸入n的大小無關，只與n中1的個數有關。如果n的二進制表示中有M個1，那么這個方法只需要循環k次即可，所以其時間復雜度O(M)，代碼實現如下：
/***********************【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;}新聞熱點
疑難解答
