文档章节

LeetTravel-461

阿泽啊
 阿泽啊
发布于 2017/05/12 15:43
字数 616
阅读 1
收藏 0
点赞 0
评论 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
博文 7
码字总数 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
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
iOS5.1下emoji表情显示方框的解决办法

iOS5.1下emoji表情显示方框的解决办法 在iOS5.1的部分设备上,emoji表情无法正常显示.我测试了一下,iOS5.1(9B176 for iPhone 4)无法正常显示emoji,全部是方框 iOS5.1(9B179 for iPhone 4S)上面...

长平狐
2012/08/13
277
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
0
0
Manjaro Linux 0.8.1 发布

Manjaro Linux是面向桌面的、用户友好的、基于Arch Linux的发行。它的一些显著特性包括:一份直观的安装程序、自动硬件检测、用于管理图形卡的特别Bash脚本、一组额外的桌面配置选项。 Manj...

oschina
2012/09/21
775
0
[力荐] 目前最好的中文WP7开发教程哦!

目 录 1、 准备工作: Windows Phone 7 开发环境搭建 Windows Phone 7 Series 开发问答 Windows Phone 7第一次亲密接触 2 、进阶开发: Windows Phone 7 Application Controls Windows Phone...

虫虫
2011/11/21
3.6K
18
深度学习:SqueezeNet、GoogLenet

SqueezeNet paper: https://arxiv.org/abs/1602.07360 code: https://github.com/DeepScale/SqueezeNet 以下这些博文整理的以及相当全面,记录一下 1.SqueezeNet: AlexNet-level accuracy w......

lilai619
2017/01/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

32.filter表案例 nat表应用 (iptables)

10.15 iptables filter表案例 10.16/10.17/10.18 iptables nat表应用 10.15 iptables filter表案例: ~1. 写一个具体的iptables小案例,需求是把80端口、22端口、21 端口放行。但是,22端口我...

王鑫linux
今天
0
0
shell中的函数&shell中的数组&告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析

影夜Linux
今天
0
0
Linux网络基础、Linux防火墙

Linux网络基础 ip addr 命令 :查看网口信息 ifconfig命令:查看网口信息,要比ip addr更明了一些 centos 7默认没安装ifconfig命令,可以使用yum install -y net-tools命令来安装。 ifconfig...

李超小牛子
今天
1
0
[机器学习]回归--Decision Tree Regression

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很...

wangxuwei
昨天
1
0
Redis做分布式无锁CAS的问题

因为Redis本身是单线程的,具备原子性,所以可以用来做分布式无锁的操作,但会有一点小问题。 public interface OrderService { public String getOrderNo();} public class OrderRe...

算法之名
昨天
9
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
昨天
1
0
数据结构与算法1

第一个代码,描述一个被称为BankAccount的类,该类模拟了银行中的账户操作。程序建立了一个开户金额,显示金额,存款,取款并显示余额。 主要的知识点联系为类的含义,构造函数,公有和私有。...

沉迷于编程的小菜菜
昨天
1
0
从为什么别的队伍总比你的快说起

在机场候检排队的时候,大多数情况下,别的队伍都要比自己所在的队伍快,并常常懊悔当初怎么没去那个队。 其实,最快的队伍只能有一个,而排队之前并不知道那个队快。所以,如果有六个队伍你...

我是菜鸟我骄傲
昨天
1
0
分布式事务常见的解决方案

随着互联网的发展,越来越多的多服务相互之间的调用,这时候就产生了一个问题,在单项目情况下很容易实现的事务控制(通过数据库的acid控制),变得不那么容易。 这时候就产生了多种方案: ...

小海bug
昨天
3
0
python从零学——scrapy初体验

python从零学——scrapy初体验 近日因为一些事情,需要从网上爬取一些东西,故而想通过使用爬虫来顺便学习下强大的python。现将一些学习中遇到的问题记录下来,以便日后查询 1. 开发环境的准...

咾咔叽
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部