leetcode_1--easy--汉明距离

2019-11-06 08:55:09

字体：大中小

来源：转载

供稿：网友

Hamming Distance介绍

给定2个整数x和y，二进制格式中同一位置值不同的个数n，就是hamming 距离(0 <= n <=31)。比如：x=4，y=1，对应的二进制：x=0100, y=0001, 在第1和第3位不同，则4和1的汉明距离是2。

最初解题思路+代码

最初的想法是：同时求x和y的二进制值，比较每个bit上的值是否相等。其中二进制值通过商和余数的迭代得到。

int hammingDistance_v1(int x, int y) { //初始化参数 int dist = 0; int shangHigh, shangLow, yuHigh, yuLow; shangHigh = x; shangLow = y; do{ yuHigh = shangHigh % 2; yuLow = shangLow % 2; if (yuHigh != yuLow) { ++ dist; } //下一次计算的基数 shangHigh = floor(shangHigh / 2); shangLow = floor(shangLow / 2); }while(shangHigh || shangLow); return dist; }

在十进制上计算，逻辑简单明了，运行时间约3ms。但是，学过计算机基础的都知道，在计算机的底层，每个字符都是用0和1表示的，通过换算成十进制或其他字体是为了提高可读性。更高级的方式就是直接用二进制运算方式解答：

按位运算包括：^，&， | , ~, >>, <<^, & , |是双目运算，而~, >>, <<是单目运算。^ 是异或运算，当二进制中bit同为1或0时，该bit的异或值=0； bit不同时，异或值=1。比如：4^1=0100 ^ 0001 = 0101 = 5& 是与运算，当bit同为1时，该bit的与值=1；否则都为0。比如：4&1=0100&0001=0000=0| 是或运算，当bit中有一个为1时，该bit的或值=1，当都为0时，或值=0。比如：4|1=0100 | 0001 = 0101 = 5~ 是取反运算，~x是对每个bit取补值。比如：~4=~0100=1011=11>>是右移运算，x>>1是向右移1位。比如：4>>1=0100>>1=0010=2<<是左移运算，x<<1是向左移动1位。比如：4<<1=0100<<1=1000

用异或运算计算x和y的汉明距离流程：

n=x^y;n的二进制中有几个1，二进制=迭代计算商%2 代码如下： int hammingDistance(int x, int y) { int xorValue = x ^ y; int dist = 0; //计算xor的1个数 do { if (xorValue % 2) { ++ dist; } xorValue = xorValue / 2; }while(xorValue); return dist; }

进阶算法

异或运算算是比较高级的用法了，那我们怎么改进算法呢？就集中在（2）上。

1. &和位移运算

计算n的二进制值中最末一位bit是否为1，迭代右移遍历所有bit位。

int hammingDistance(int x, int y) { int xorValue = x ^ y; int dist = 0; int tmp = 0; //计算1的个数 while(xorValue) { tmp = xorValue & 1; //最后一位bit是否=1 if (tmp == 1){ ++ dist; } xorValue = xorValue >> 1; } return dist; }

2. 数学方式

n & (n-1)可以消除n的最末一位1，比如： n=7=111, n-1=6=110, 则n & (n-1) = 111 & 110 = 110 n=112=111 0000, n-1=111=110 1111, n & (n-1) = 111 0000 & 110 1111 = 110 0000 可以看出，n & (n - 1)能消除有效位中最后一个1的影响。究其原因，二进制的每位bit上不是0就是1，每个数字其本质不是1，就是通过不断+1进位得到的， n & (n - 1) 去除了最末位1及其进位的影响。这样，二进制中有几个1就变得简单了，不断循环 n = n & (n -1)，直到n=0。代码如下：

int hammingDistance(int x, int y) { int xorValue = x ^ y; int dist = 0; //计算1的个数 while(xorValue) { xorValue = xorValue & (xorValue - 1); ++ dist; } return dist; }