首页 > 代码库 > 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 ≤ 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.
分析
"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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。