首页 > 代码库 > 461. Hamming Distance

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 ≤ xy < 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.

分析

"corresponding bits are different"即"异或"运算,Java中"异或运算符"的符号为^

(例:a的值是15,转换成二进制为1111;b的值是2,转换成二进制为0010。则a^b的结果为1101,即13。)

此题可转化为:求x异或y的结果的二进制表达式中‘1‘的个数

解答

解法1:(我)遍历二进制字符串(最复杂)

将x异或y的结果转化为二进制字符串,遍历所有字符,求‘1‘的个数

 1 public class Solution {
 2     public int hammingDistance(int x, int y){
 3         String str = Integer.toBinaryString(x ^ y);//或Integer.toString(x ^ y , 2)
 4         int count = 0;
 5         for (int i = 0; i < str.length(); i++){
 6             if (str.charAt(i) == ‘1‘){
 7                 count++;
 8             }
 9         }
10         return count;
11     }
12 }

 

解法2:求二进制字符串差值

将x异或y的结果转化为二进制字符串,将其中所有"1"替换为""(空字符串),求替换前后字符串长度差值

1 public class Solution {
2     public int hammingDistance(int x, int y){
3         String str = Integer.toBinaryString(x ^ y);//或Integer.toString(x ^ y , 2)
4         String str2 = str.replaceAll("1","");
5         return str.length() - str2.length();
6     }
7 }

 

解法3:使用系统内置函数Integer.bitCount()

1 public class Solution {
2     public int hammingDistance(int x, int y) {
3         return Integer.bitCount(x ^ y); //返回指定int值的二进制补码表示形式的1位的数量
4     }
5 }

 

解法4:位运算(>>, &)

计算xor & 1,若xor末位为1,结果为1;若xor末位为0,结果为0。将结果记入count。再将xor右移1位。重复上述过程,直到xor右移到尽头(xor == 0)

0101 ---> 010 ---> 01 ---> 0

 1 public class Solution {
 2     public int hammingDistance(int x, int y){
 3         int xor = x ^ y;
 4         int count = 0;
 5         while (xor != 0){
 6             count += xor & 1;
 7             xor >>= 1;
 8         }
 9         return count;
10     }
11 }

 

461. Hamming Distance