计算一个无符整数中1Bit的个数

《计算一个无符整数中1Bit的个数》由会员分享，可在线阅读，更多相关《计算一个无符整数中1Bit的个数（4页珍藏版）》请在装配图网上搜索。

1、计算一个无符整数中 1Bit 的个数Count the number of bits that are on in an unsigned integer 这是一个经常遇到的经典问题，这里分两个部分讲解和总结，首先对讲解现有的算法，然后 再讲解一些改进算法。1 循环法(Iterated Count)int bitcount (unsigned int n)int count=0;while (n)count += n & 0x1u ; n = 1 ; return count ;最容易理解和想到的方法。对每一位依次判断是否为1,如果是就在count上加1。循环的次数是常数(n的位数)。在1比较

2、稀疏的时候效率低，可用方法2改进。2 Bitl 稀疏 Sparse Onesint bitcount (unsigned int n)int count=0 ;while (n)count+ ; n &= (n - 1) ; return count ;理解这个算法的核心，只需理解2个操作：1当一个数被减1时，他最右边的那个值为1的Bit将变为0,同时其右边的所有的Bit都 会变成1。2“&=”，位与并赋值操作。去掉已经被计数过的 1，并将改值重新设置给 n.这个算法循环的次数是bit位为一的个数。也就说有几个Bit为1,循环几次。对Bit为1比 较稀疏的数来说，性能很好。如：0x1000 0

3、000,循环一次就可以。3密集 1的算法 Dense Onesint bitcount (unsigned int n) int count = 8 * sizeof(int) ;n A= (unsigned int) -1 ;while (n)count- ;n &= (n - 1) ;return count ;与 2 稀疏 1 的算法相类似。不同点是，针对 1 密集的情况，循环的次数会大大减少。他的循 环次数：sizeof(int)-Bit 1的个数。48bit 静态表查找法 Precompute_8bitstatic int bits_in_char 256 = 0, 1, 1, 2,

4、 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,3, 4, 4, 5, 3,

5、4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,3, 4, 4, 5, 4, 5, 5

6、, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,6, 7, 6, 7, 7, 8;int bitcount (unsigned int n)/ works only for 32-bit intsreturn bits_in_char n & 0xffu+ bits_in_char (n 8) & 0xffu+ bits_in_char (n 16) & 0xffu+ bits_in_c

7、har (n 24) & 0xffu ;使用静态数组表，列出所有8bit(256个)无符号数含有Bit1的个数。将32Bit的n分4部分, 直接在表中找到对应的 Bit1 的个数，然后求和。这是最快的方法了。缺点是需要比较大的内存。516bit 静态表查找法 Precompute_16bit因为在计算 64 位 int 时，以上方法 4 并不总是最快，所以有以下的一个进化版，就是用十 六 Bit 的表来作驱动映射。这样需要的内存就更大了。static char bits_in_16bits 0x1u 16) & 0xffffu ;6. 合并计数器法 Parallel Counterunsign

8、ed numbits(unsigned int i)unsigned int const MASK1 = 0x55555555;unsigned int const MASK2 = 0x33333333;unsigned int const MASK4 = 0x0f0f0f0f;unsigned int const MASK8 = 0x00ff00ff;unsigned int const MASK16 = 0x0000ffff;/*MASK1 = 01010101010101010101010101010101MASK2 = 00110011001100110011001100110011M

9、ASK4 = 00001111000011110000111100001111MASK8 = 00000000111111110000000011111111MASK16 = 00000000000000001111111111111111*/i = (i&MASK1 ) + (i1 &MASK1 );i = (i&MASK2 ) + (i2 &MASK2 );i = (i&MASK4 ) + (i4 &MASK4 );i = (i&MASK8 ) + (i8 &MASK8 );i = (i&MASK16) + (i16&MASK16);return i;这个算法是一种合并计数器的策略。把输入

10、数的32Bit当作32个计数器，代表每一位的1 个数。然后合并相邻的2个“计数器”使i成为16个计数器，每个计数器的值就是这2个 Bit的1的个数；继续合并相邻的2个“计数器“，使i成为8个计数器，每个计数器的值 就是4个Bit的1的个数。依次类推，直到将i变成一个计数器，那么它的值就是32Bit的 i 中值为 1 的 Bit 的个数。举个例子，假设输入的 i 值为 10010111011111010101101110101111(十进制 2541575087)计算过程如下：(共22个1)1. 将 32 个计数器合并为 16 个,每一个计数器代表 2-bit 的 1 个数1 0 0 1 0 1

11、 1 0 0 0 1 1 1 1 1 1 = 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1+0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 = 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 2 1 2 2 1 1 1 1 2 1 1 2 2 = 01 01 01 10 01 10 10 01 01 01 01 10 01 01 10 102. 将16 个计数器合并为8 个,每一个计数器代表 4-bit 的1个数1 1 1 2 1 1 1 2 = 01 01 01 10 01 01 01 10+1 2 2 1 1 2 1 2 = 0

12、1 10 10 01 01 10 01 102 3 3 3 2 3 2 4 = 0010 0011 0011 0011 0010 0011 0010 01003. 将8个计数器合并为4个,每一个计数器代表 8-bit 的1 个数3 3 3 4 =0010 0011 0010 0010+2 3 2 2 =0011 0011 0011 0100 5 6 5 6 = 00000101 00000110 00000101 000001104. 将4个计数器合并为2个,每一个计数器代表 16-bit 的 1个数5 5 = 00000101 00000101+ 6 6 = 00000110 0000011

13、0 11 11 = 0000000000001011 00000000000010115. 最后，将2个计数器合并为1个，每一个计数器代表32-bit (也就是输入的值i)的1个 数11 = 0000000000001011+11 = 0000000000001011 22 = 00000000000000000000000000010110 对于该算法的实现，另外有一种比较好的写法，这种算法避免了使用常数宏，使比较通用的 实现：#define TWO(c) (0x1u (TWO(c) & MASK(c)int bitcount (unsigned int n)n = COUNT(n, 0) ;n = COUNT(n, 1) ;n = COUNT(n, 2) ;n = COUNT(n, 3) ;n = COUNT(n, 4) ;/* n = COUNT(n, 5) ; for 64-bit integers */return n ;