文档章节

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

© 著作权归作者所有

共有 人打赏支持
上一篇: LeetTravel-557、476
下一篇: LeetTravel-520
阿泽啊
粉丝 0
博文 11
码字总数 5063
作品 0
美国
私信 提问
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
LeetCode 477 Total Hamming Distance

LeetCode 排列组合 题目汇总 LeetCode 数字 题目汇总 LeetCode 动态规划 题目分类汇总 干货!LeetCode 题解汇总 题目描述 The Hamming distance between two integers is the number of pos...

被称为L的男人
2017/12/10
0
0
spring中使用c3p0

各位大神,小弟有个问题请教。在spring中用c3p0做数据源,测试代码测试通过,但是后台总是报错,请帮我看看啊,如下: at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(...

chen3shi
2013/11/20
3.6K
2
Radstudio 10.2.3 (Delphi 10.2.3 C++builder )

官方下载地址: http://altd.embarcadero.com/download/radstudio/10.2/delphicbuilder10_2_3_2631.iso ftp://ftpd.embarcadero.com/download/radstudio/10.2/delphicbuilder10_2_3_2631.iso......

vga
03/14
0
0
eclipse 导入的项目tomcat出现的问题 大佬帮看看

14:10:45,004 DEBUG DefaultListableBeanFactory:509 - Eagerly caching bean 'managerTx' to allow for resolving potential circular references 14:10:45,045 DEBUG StandardEnvironment:......

辰南方
05/10
106
3

没有更多内容

加载失败,请刷新页面

加载更多

容器之Zookeeper的使用

我们使用zookeeper时,都是在Linux上安装zookeeper,之后启动时要加入配置文件。 使用docker之后,我们可以直接使用镜像运行容器,镜像可以从docker.hub上下载,地址是https://hub.docker.co...

克虏伯
昨天
1
0
esxi 更换ssl证书

概述 就是想换一个证书而已,你可以通过下面的途径去申请一个泛解析域名的证书之后再esxi上安装上 使用阿里云域名api申请Let’s Encrypt泛域名免费ssl证书 申请完成证书之后进行下一步 操作 ...

bboysoulcn
昨天
1
0
PLC编程入门:梯形图

梯形图(LAD)是PLC编程的最佳可视化语言,它看起来非常类似于继电器电路图,因此如果 你对继电器控制和电子电路有所了解的话,那么学起来会非常容易! 在这个教程中,我们将学习关于使用梯形...

汇智网教程
昨天
1
0
Kubernetes 1.13.0的快速升级

Kubernetes 1.13.0已经正式发布,快速升级(含国内镜像快速下载链接)包括升级kubeadm/kubectl/kubelet版本、拉取镜像、升级Kubernetes集群三个主要步骤。注意Kubernetes 1.13.0版本暂时不支...

openthings
昨天
2
0
go的卸载和环境变量配个人.bashrc

若是用安装包直接解压 http://download.csdn.net/detail/u010026901/7592581 cd /usr/local tar -zxvf go1.1.2.linux-386.tar.gz(先把安装包移到这个目录) 3.安装 $ cd go/src,$ ./all.b......

dragon_tech
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部