个数的二进制中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位的数,…
更多推荐
求解一个数的二进制中1的数量
发布评论