求解一个数的二进制中1的数量

个数的二进制中1的数量"/>

求解一个数的二进制中1的数量

假设二进制数是 11
(11 & 01) + ((11 >>> 1) & 01) = 01 + 01 = 10 => 2

假设二进制数是 1011
(1011 & 0101) + ((1011 >>> 1) & 0101) = 0001 + 0101 = 0110 => 整体无意义，结果每两位表示二进制数每两位中1的数量
(0110 & 0011) + ((0110 >>> 2) & 0011) = 0010 + 0001 = 0011 => 3

比如计算java中一个int类型的数，其二进制中1的数量

public int bitCount(int i){i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);return i;
}

总结，这是一个不断压缩的过程，获得每2位的数，再把每2位的数求和，得到每4位的数，再把每4位的数求和，得到每8位的数，…