文档章节

LeetTravel-461

阿泽啊
 阿泽啊
发布于 2017/05/12 15:43
字数 616
阅读 1
收藏 0

计算汉明距离:

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

 如果一个整数不为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
博文 11
码字总数 5063
作品 0
美国
DiskGenius 4.6.1 发布,磁盘分区和数据恢复

DiskGenius是一款集磁盘分区管理与数据恢复功能于一身的工具软件。它即是一款功能强大、灵活易用的分区软件,同时也是一款技术高超、功能全面的数据恢复软件。它不仅具备与分区管理有关的几乎...

oschina
2014/05/20
916
0
android 连接 .net webservice 上传图片 异常 求大神知道

11-16 14:31:54.461: W/System.err(9804): SoapFault - faultcode: 'soap:Server' faultstring: 'Server was unable to process request. ---> The OleDbParameterCollection only accepts n......

孙振邦
2013/11/16
178
0
Android Studio 2.2 Beta 2 发布

Android Studio 2.2 Beta 2 发布,包含了大量的 bug 修复 Unit Test and Test Issues generally should now be working again. Gradle and Gradle Plugin Bug Fixes including around pro g......

NextLife
2016/08/19
1K
5
Android Studio 2.2 Beta 发布

Android Studio 2.2 Beta 发布了。 此版本包含了大量的bug修复,更新如下: Constraint Layout and New Layout Editor Bug fixes Improvements to the interaction between Gradle 2.14.1 an......

oschina
2016/08/10
3.3K
15
java.lang.SecurityException: Permission denied (missing INTERNET permission?)

E/AndroidRuntime: FATAL EXCEPTION: Thread-4 Process: com.easy.kotlin, PID: 5384 java.lang.SecurityException: Permission denied (missing INTERNET permission?) at java.net.Inet6Ad......

程序员诗人
2017/10/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS 7.* 配置网络

配置静态IP 进入配置文件目录 cd /etc/sysconfig/network-scripts 查找以 ifcfg-eno 开头的文件并编辑它 vi ifcfg-ens32 修改文件中的变量值 BOOTPROTO=staticONBOOT=yesIPADDR=192.168...

阿白
29分钟前
0
0
深入理解OAuth2.0协议

1. 引言 如果你开车去酒店赴宴,你经常会苦于找不到停车位而耽误很多时间。是否有好办法可以避免这个问题呢?有的,听说有一些豪车的车主就不担心这个问题。豪车一般配备两种钥匙:主钥匙和泊...

xtof
33分钟前
1
0
Linux学习-0920

3.4 usermod命令 3.5 用户密码管理 3.6 mkpasswd命令 一、usermode命令 usermode作用是用来修改用户信息。 方法: usermod 参数 username 示例1:修改用户uid usermod -u 1010 test5 示例2...

wxy丶
43分钟前
1
0
synchronized锁对象的坑

今天本来写点其他东西,碰巧写了一下synchronized,没想到掉坑里面了,大佬别笑。 起初代码大概是这样的: package com.ripplechan.part_1_2_3;import java.util.concurrent.CountDownL...

RippleChan
46分钟前
1
0
XAMPP环境搭建(Apache + MariaDB + PHP + Perl)

operation system:ubuntu-18.04.1 step1:download XAMPP #sudo wget https://www.apachefriends.org/xampp-files/7.2.9/xampp-linux-x64-7.2.9-0-installer.run step2:install XAMPP #sudo ......

硅谷课堂
48分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部