编程能力提高班2:Hamming Distance

2018-02-06 09:42:50来源:https://www.jianshu.com/p/bebf17f18946作者:调侃熊人点击

分享






普通解法

难点有两处:


十进制转二进制
如果位数不足,需要用0来填充
int hammingDistance(int x, int y) {
string x1=decToBin(x);
string y1=decToBin(y);
while(x1.size()!=y1.size()){
if(x1.size()>y1.size())
y1.append("0");
else x1.append("0");
}
int count=0;
for(int i=x1.size()-1;i>=0;i--){
if(x1[i]!=y1[i]) count++;
}
return count;

}
string decToBin(int dec){
string bin="";
for(int i=dec;i;i=i/2){
bin+=(i%2?"1":"0");
}
if (dec==0) {return "0";}
else return bin;
}

但是这样的算法并不理想,我们来看看运行时间:






显然上述的算法很费时间,下面给大家带来高级解法。
高级解法
int hammingDistance(int x, int y) {
int res = 0, exc = x ^ y;
while (exc) {
++res;
exc &= (exc - 1);
}
return res;

对于^运算符:

高级解法利用了异或运算符^,他返回的是两个数字的二进制进行异或计算后,这个二进制对应的十进制的值



1^4==5



对于&=:

这是按位进行and操作,比如上面的exc &=(exc-1),它的意义就是移除exc最右边的bit 1。
这样操作的意义是什么?我们拿dec 1 bin 1和dec 4 bin 100作比较:100^001==101,细心的你是否发现,101中1的个数其实就代表了原来两个二进制中,有多少个不同位。
基于这个思想,我们只要统计出1的个数,就圆满完成任务,我想到一个很巧妙的方法,exc&(exc-1)
我们就拿1010101举例:
1010101-1=1010100
1010101 and 1010100=1010100 //去掉了最右边的1
1010100-1=1010011
1010100 and 1010011=1010000 //去掉了最右边的1
...
最后将得到:0000000
因此我只用一个while循环,每次res++,于是就得到了1的个数


总结

好的方法,往往令人百得不思其解,但其中的精髓确是妙不可言。好的算法充满了捷径,如果能跳出固有思维的强,真的可以事半功倍!
这次的进制转换显然多此一举,其次,许多不必要的遍历操作,完全可以用and来替代








最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台