汉明距离（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); } }