【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 - C
int hammingDistance(int x, int y) {
int tmpInt=x^y;
int dis=0;
while(tmpInt)
{
if((tmpInt>>1)<<1 != tmpInt)
{
++dis;
}
tmpInt>>=1;
}
return dis;
}
解题思路
异或:相同为0,相异为1.
利用异或的特性,先将两数x和y做异或运算。得到的结果tmpInt中,为1的位表示x和y中不相同的位置。将tmpInt先右移再左移,此时若tmpInt还等于原来的tmpInt,则表示最低位为0,否则为1。记录tmpInt中1的个数,即x和y不同位的个数。
解决方案2
int hammingDistance(int x1, int x2) {
int b1[32];
int b2[32];
int r1 = x1;
int r2 = x2;
int i = 0, j = 0;
while(r1 > 0){
b1[i++] = r1 % 2;
r1 = r1 >> 1;
}
while(r2 > 0){
b2[j++] = r2 % 2;
r2 = r2 >> 1;
}
int ans = 0;
for(int k = 0; k < i && k < j; k++){
if(b1[k] != b2[k]){
ans++;
}
}
if(i > j){
for(int k = j; k < i; k++){
if(b1[k] != 0){
ans++;
}
}
}else{
for(int k = i; k < j; k++){
if(b2[k] != 0){
ans++;
}
}
}
return ans;
}
解题思路
将十进制的x和y的二进制形式存放到b数组中(每次除以2的余数),然后比较两个b数组中不同位数的个数,最后注意不同长度的问题(位数较多的数,记录长出的部分1的个数)。
解决方案 - java
public class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
解题思路
What does come to your mind first when you see this sentence "
corresponding bits are different"? Yes,XOR! Also, do not forget there is a decent function Java provided:Integer.bitCount().
bitCount实现几种实现方式(牛逼)
[Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论