汉明距离（ Hamming Distance ）的基本思想很简单，就是找不同。当求由01二进制组成 的向量间的汉明距离可以由位运算直接进行，速度非常快。好的算法能让计算速度达到极快，Java内置bitCount源码就实现了一种速度极快的算法。在Linux机器 （CPU: i7-4790 @ 3.6GHz）测试了1亿对汉明距离只用0.5ms，是普通算法的196倍。

测试1亿对汉明距离结果

测试基于32位的01二进制数进行的。

import java.util.Arrays ; import java.util.Random ; public class testHammingDistance { //生成1亿个随机32位的Int类型数 public static int [] randomInt ( int num , int seed ) { int [] a = new int [ num ]; Random r = new Random ( seed ); Arrays . setAll ( a , w -> r . nextInt ()); return a ; //调用Java bitCount 求汉明距离 public static int hammingDistance1 ( int hash1 , int hash2 ) { int i = hash1 ^ hash2 ; return Integer . bitCount ( i ); //求解正数的二进制汉明距离 public static int hammingDistance2 ( int hash1 , int hash2 ){ int num = hash1 ^ hash2 ; int count = 0 ; for (; num > 0 ; count ++) num &= ( num - 1 ); return count ; //主函数测试1亿对 public static void main ( String [] args ) { int tem = 4324523 ; int [] all = randomInt ( 100000000 , 123 ); long startTime = System . currentTimeMillis (); for ( int x: all ){ int tem1 = hammingDistance1 ( tem , x ); long endTime = System . currentTimeMillis (); long startTime2 = System . currentTimeMillis (); for ( int x: all ){ int tem2 = hammingDistance2 ( tem , x ); long endTime2 = System . currentTimeMillis (); System . out . println ( "hammingDistance1 time used: " + ( endTime - startTime ) + "ms" ); System . out . println ( "hammingDistance2 time used: " + ( endTime2 - startTime2 ) + "ms" ); hammingDistance1 time used: 5ms hammingDistance2 time used: 980ms Process finished with exit code 0

求汉明距离的核心是在数两个二进制数求 & 运算后1的个数，求1的个数最容易想到的是循环整个二进制获得1的个数。如下算法:

public int numberOf1 ( int hash1 , int hash2 ){ int num = hash1 ^ hash2 ; int count = 0 ; while ( n != 0 ){ if (( num & 1 ) == 1 ){ ++ count ; n = n >> 1 ; return count ;

这种方法很容易理解，就是每次循环的时候对1取 & 操作，若结果等于1就统计出了一个1，然后每次循环后右移 >> 使高位的0或1移动到低位。这种算法的 时间复杂度为 O(n) ,其中n表示bit的位数。

public int hammingDistance2 ( int hash1 , int hash2 ){ int num = hash1 ^ hash2 ; int count = 0 ; for (; num > 0 ; count ++) num &= ( num - 1 ); return count ;

优化后的方法通过二进制的运算法则进行优化，优化后的时间复杂度仍然为 O(n) ，但是这里的n代表着1的个数最差的结果n才代表bit位，比第一个算法n代表bit位要好。 二进制的运算原则是逢二进一，每次循环时候我都让num减去1通过跟自身&操作消除低位1，最后num<0循环停止。有多少个1就循环多少次。

例如，二进制 0b1110 统计为3个1的过程如下：

// 第一次迭代: 0b1110 - 1 = 0b1110 - 0b0001 = 0b1101 0b1110 & 0b1101 = 0b1100 // 第二次迭代： 0b1100 - 1 = 0b1100 - 0b0001 = 0b1011 0b1100 & 0b1011 = 0b1000 // 第三次迭代： 0b1000 - 1 = 0b1000 - 0b0001 = 0b0111 0b1000 & 0b0111 = 0b0000

Java源码bitCount算法

Java的32位二进制Integer.bitCount源码如下：

public static int bitCount ( int i ) { i = i - (( i >>> 1 ) & 0x55555555 ); i = ( i & 0x33333333 ) + (( i >>> 2 ) & 0x33333333 ); i = ( i + ( i >>> 4 )) & 0x0f0f0f0f ; i = i + ( i >>> 8 ); i = i + ( i >>> 16 ); return i & 0x3f ;

Java源码实现了复杂度为O(1)的算法

当我们想知道一个二进制数中有多少个1时候最容易想到的方法就如前两种方法一个一个的数，数一下一共多少个1就完事了。但是Java源码使用的方法是 先两个一对儿数一下有多少个1，存到原来的位置。然后对上面的数的结果再成对统计以此类推。

以8位为例，算法思想如下：

二进制 十进制 ( count个数 ) 1 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 \/ \/ \/ \/ \/ \/ \/ \/ 01 10 10 01 1 2 2 1 \ / \ / \ / \ / 0011 0011 3 3 \ / \ / 0110 6

这种count方法就如一个倒立的二叉树一样。每一层的节点个数为2^(n-1)个，也就是说对于32位的二进制2^(n-1)=32，n=5。所以，我们只需要数5次，对于64位二进制只需要 数6次就能知道二进制中有多少个1了，这种方法实现了时间复杂度为O(1)优秀算法。

Java源码算法实现机理

Java源码中每次 & 运算各个数的二进制，主要是为了抹除成对统计时候的左位（进行右移位运算时候高位对低位产生的影响）。

0x55555555 ‭ 0b01010101010101010101010101010101 ‬ 0x33333333 ‭ 0b00110011001100110011001100110011 ‬ 0x0f0f0f0f ‭ 0b00001111000011110000111100001111 ‬ 0x00ff00ff 0b00000000111111110000000011111111 0x0000ffff ‭ 0b00000000000000001111111111111111 ‬ 0x3f ‭ 0b00111111 ‬

i & 0x55555555实现整数i抹除左一位，然后错位相加。 (i »> 1) & 0x55555555表示：左位移到右边，再把左位抹除，这样就可以计算两个bit位上1的个数了：0b1011=>0b0001 + 0b0101 = 0b0110左两位有1个1，右两位有2个1。 这时i中存储了每两位的统计结果，可以进行两两相加，最后求和