LeetTravel-461
LeetTravel-461
阿泽啊 发表于11个月前
LeetTravel-461
  • 发表于 11个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

计算汉明距离:

算法和数学的重要性!!!思想决定了方法的高度!!所谓磨刀不误砍柴工!

 如果一个整数不为0,那么这个整数至少有一位是1。如果我们把这个整数减去1,那么原来处在整数最右边的1就会变成0,原来在1后面的所有的0都会变成1。其余的所有位将不受到影响。举个例子:一个二进制数1100,从右边数起的第三位是处于最右边的一个1。减去1后,第三位变成0,它后面的两位0变成1,而前面的1保持不变,因此得到结果是1011。
    我们发现减1的结果是把从最右边一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算,从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000。也就是说,把一个整数减去1,再和自己进行&运算,那么就消掉了该整数用二进制表示的最后一个1。
    一开始时,我们把要求的两个整数进行异或运算(实际是整数的二进制形式进行异或运算),这样相同为0,不同为1,也就是这个整数M的二进制表示中,1的个数就是整数X和Y的二进制不同位数的个数;接下来就只需要计算M的二进制表示中1的个数即可。由上所述,通过把整数与整数减1做与运算,可以消掉该整数二进制表示的最后一个1,那么我们就算一下需要消多少次,即是M的1的个数,也即是X和Y的二进制不同位数的个数
这样,我们就可以通过上述方法统计一共有多少不同的1,这就是最后的答案。

异或运算的性质:
1.任意一个变量X与其自身进行异或运算,结果为0,即X^X=0

2.任意一个变量X与0进行异或运算,结果不变,即X^0=X

3.异或运算具有可结合性,即a^b^c=(a^b)^c=a^(b^c)

4.异或运算具有可交换性,即a^b=b^a

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 7
码字总数 5063
×
阿泽啊
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: