十进制中二进制表示法中1的个数之汉明算法

1. 汉明距离概念说明

汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：

1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
“toned” 与 “roses” 之间的汉明距离是 3。

汉明重量
汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是 1 的个数，所以 11101 的汉明重量是 4。

2. java代码实现

public class HanMing{
	public int count(int data){
		  data = (data & 0x55555555) + ((data >> 1) & 0x55555555);
        System.out.println("step1:" + Integer.toBinaryString(data));
        data = (data & 0x33333333) + ((data >> 2) & 0x33333333);
        System.out.println("step2:" + Integer.toBinaryString(data));
        data = (data & 0x0f0f0f0f) + ((data >> 4) & 0x0f0f0f0f);
        System.out.println("step3:" + Integer.toBinaryString(data));
        data = (data * (0x01010101) >> 24);
        System.out.println("step4:" + Integer.toBinaryString(data));
        return data;
	}
	public static void main(String[] args) {
        HanMing hanMing = new HanMing();
        int data = 15;
        System.out.println("data:" + Integer.toBinaryString(data));
        System.out.println(hanMing.hanming(data));
    }
}

输出：

data:1111
step1:1010
step2:100
step3:100
step4:100
4

3. 步骤详解

步骤1：计算出的值data的二进制表示可以按每两个二进制位位一组进行分组，各组的十进制表示就是该组的汉明重量。1001+0001 = 1010，（每个组代表2）
步骤2：计算出的值data的二进制表示可以按每四个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量。0010+0010=0100，（每个组代表4）
步骤3：计算出的值data的二进制表示可以按每八个二进制位为一组进行分组，各组的十进制表示就是该组的汉明重量。0100+0000=0100，（每个组代表4）
步骤4：data*0x01010101语句计算出bitarray的汉明重量并记录在二进制的最高八位，而>>24语句则通过右移运算，将bitarray的汉明重量移动到最低八位，得出的结果就是bitarray的汉明重量。

参考：redis设计与实现第二版，汉明概念参考：百度百科