461. 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2

题解思路：
1、找两个数字对应二进制位不同的位置的数目，用异或
2、然后逐个右移，跟1相与，计数即可

  1. class Solution {
  2.     public int hammingDistance(int x, int y) {
  3.         int k = x ^ y;
  4.         //此时问题变为了统计一个数的二进制中1的个数
  5.         int count = 0;
  6.         while (k > 0) {
  7.             if ((k & 1) == 1)
  8.                 count++;
  9.             k = k >> 1;
  10.         }
  11.         return count;
  12.     }
  13. }

布赖恩·克尼根算法
题解思路：遇到最右边的1后，跳过中间的0，直接跳到下一个1。
13、位运算 - 图1

class Solution {
    public int hammingDistance(int x, int y) {
        int k = x ^ y;
        //此时问题变为了统计一个数的二进制中1的个数
        int count = 0;
        while (k > 0) {
            count++;
            k = k & (k - 1);
        }
        return count;
    }
}