汉明距离（Hamming Distance）

LeetCode 191 Number of 1 Bits

计算一个数字的比特位包含1的个数

思路1：将其转换成二进制，计算其中1的个数（见下面代码注释部分），时间复杂度：O(n)，n为二进制长度。
思路2：有个小技巧：value &= value - 1这个运算的结果就是把value最后一个1去掉，循环进行运算直到value等于0（所有的1都被去掉）就可以知道vaule拥有多少个1了，时间复杂度：O(m)，m为1的个数。

public class LeetCode191 {
     public int hammingWeight(int n) {
         int len = 0;
         /*
            String bin = Integer.toBinaryString(n);
            for (int i = 0; i < bin.length(); i++) {
                if(bin.charAt(i) == '1')
                    len++;
            }
            */
        //在Java中，不存在Unsigned无符号数据类型，但可以轻而易举的完成Unsigned转换,此处不做转换，while条件为n != 0 而不是n > 0(可能存在负数符号为1)  
         while(n != 0){    
             n = n & n - 1;
             len++;
         }
            return len;
        }
}

LeetCode 461 Hamming Distance

海明距离：任意两个数在二级制的表示下（int = 32bit），每个bit对应的值是1或0，那么这两个数在这32个位置下，取值不一样的地方的总和就是海明距离。

思路1：

• 对两数异或之后求二进制数，然后计算二进制中多少个1即是两者的海明距离。

代码1：

public class LeetCode461 {
     public int hammingDistance(int x, int y) {
            String c = Integer.toBinaryString(x ^ y);
            int count = 0;
            for (int i = 0; i < c.length(); i++) {
                if(c.charAt(i) == '1')
                    count ++;
            }
            return count;
        }
}

思路2：

• 利用小技巧：value &= value - 1

代码2：

public class LeetCode461V {
     public int hammingDistance(int x, int y) {
           int n = x ^ y ;
           int len = 0;
           while(n > 0){
                n = n & n - 1;
                len++;
            }
            return len;
     }
}

LeetCode 477 Total Hamming Distance

总的汉明距离：该数组中，所有两两组合得到的元素的海明距离的和。

思路

• int长度是32bit，一共n个数
• 在每个位置上，如果有k个数为1，那么就有n-k个为0
• 那么贡献的海明距离就贡献了 k*(n-k)

代码：

public class LeetCode477 {
     public static int totalHammingDistance(int[] nums) {
         int num = 0;
         for (int i = 0; i < 32; i++) {
             int result = 0;
             for (int j = 0; j < nums.length; j++) {
             // num[j]>>i & 1 向右移动i位然后与1求与的结果，即计算num[j]的第i位是否是1
                 result = result + (nums[j]>>i) & 1; 
            }
            // 第i位海明距离就贡献了result * (nums.length - result)
             num = num +  result * (nums.length - result);
            }
         return num;
        }
     public static void main(String[] args) {
        int[] nums = {4,14,2};
        int res = totalHammingDistance(nums);
        System.out.println(res);
    }
}