求两个数的汉明距离

发表于 | 分类于 |
字数统计: 391 | 阅读时长 ≈ 2
1.源题目

汉明距离

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.

2.解决方法

方法1.暴力求解:依次对比两个数的二进制位，出现不同则加1

1.一个数A左移一位后再右移一位得到A0
2.比较A和A0，如果A和A0相等，则说明A的二进制数的最后一位为0，否则为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution{
    public int hammingDistance(int x, int y){
        int result = 0;
        int tempX = x;
        int tempY = y;
        while(tempX != 0 || tempY != 0){
            
            if(tempX == (tempX>>1)<<1){
                if(tempY != (tempY>>1)<<1){
                    result++;
                }
            }
            else{
                if(tempY == (tempY>>1)<<1){
                    result++;
                }
            }
            tempX = tempX>>1;
            tempY = tempY>>1;
        }
        return result;
    }
    public static void main(String[] args){
        Solution test = new Solution();
        System.out.println(test.hammingDistance(4, 10));       
    }
}

方法2.通过二进制运算: 两个数异或后不同位为1，相同位的值为0，如x=1，y=4

x^y = (001)^(100) = (101)

n&(n-1)则可使最后一位1变为0，计算出1的个数，即为汉明距离，解法见下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution{
    public int hammingDistance(int x, int y){
        int result = 0;
        int temp = x ^ y;
        System.out.println(temp);
        while(temp != 0){
            temp = temp&(temp-1);
            result++;
        }
        return result;
    }
    public static void main(String[] args){
        Solution test = new Solution();
        System.out.println(test.hammingDistance(1, 4));
    }
}

完整代码HammingDistance

投食