首页 > 代码库 > 从0开始的LeetCode生活—461-Hamming Distance(汉明距离)
从0开始的LeetCode生活—461-Hamming Distance(汉明距离)
题目:
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x
and y
, calculate the Hamming distance.
Note:
0 ≤ x
, y
< 231.
Example:
Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different.
题目大意:
给你两个数字,返回这两个数字的汉明距离,汉明距离就是看两个数字的二进制代码,按位异或,比如1和4,二进制分别为(0001)和(0100),一个个异或比较后得到(0101)因为第二位和第四位不一样。然后数一下得到的数有几个1.这里有两个1,所以返回2
解法:
这是一个简单的题目,先定义一个计数器和一个记录两个数字异或的变量。即int cnt=0;int e=x^y;
然后数一下e的二进制代码里面有几个1,我的做法是让它与1按位与,如果和1按位与是1,那么就说明当前最后一位是1,如果不是,那当前最后一位为0.然后再左移,直到它变为0
比如说1和4,按位与后得到的e==5(二进制为0101)
1)与1按位与,得到1,则cnt+1;
2)右移一位,得到(010),与1按位与后得到0,则cnt不改变;
3)右移,得到(01),与1按位与得到1,cnt+1;
4)右移,得到(0),与1按位与得到0,cnt不变;
5)此时e==0,退出循环,返回cnt的值,即2.
代码:
int hammingDistance(int x, int y) { int r=0,e=x^y; while(e){ if(e&1) ++r; e>>=1; } return r; }
从0开始的LeetCode生活—461-Hamming Distance(汉明距离)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。