leetcode-461-汉明距离

[题目描述]

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

上面的箭头指出了对应二进制位不同的位置。

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：

• 根据二进制10不匹配数目可联想到异或运算，最后统计为1的个数
• 实现思路可以是最开始想的异或结果以后转换成字符串统计“1”出现的次数

 public int hammingDistance(int x, int y) {
            //二进制位不同很容易想到异或
            int sum = x ^ y, res = 0;
            //然后统计异或结果1的位数即可
            String s = Integer.toBinaryString(sum);
            for (Character c: s.toCharArray()
                 ) {
                if (c == '1'){
                    res +=1;
                }
            }
        }

• 优化方案是可以通过对运算结果%2判断每一位的1的个数

 public int hammingDistance(int x, int y) {
            //二进制位不同很容易想到异或
            int sum = x ^ y, res = 0;
            //优化1 通过对2取余来做
            while (sum!=0){
                if (sum % 2 != 0){
                    res+=1;
                }
                sum /=2;
            }
            return res;
        }