C之32位二进制数内1的个数求法

《CSAPP》上的题目，略有难度。

---

问题来源

---

限制

1. 编程语言：C
2. 可用操作符：! ~ & ^ | + << >>
3. 最大操作步数：40
4. 最大操作数：255

---

思路

获取2位二进制数内”1”个数

设该数为x，则答案易得为(x & 01) + ((x >> 1) & 01)

获取4位二进制数内”1”个数

设该数为x
可以先把每两位的”1”个数求出，再加起来。

1. y = (x & 0101) + ((x >> 1) & 0101)
2. count = (y & 0011) + ((y >> 10) & 0011)

获取8位二进制数内”1”个数

设该数为x
把每两位的”1”个数求出，存储在每两位中。再把每四位的”1”个数求出，存储在每四位中。最后加起来。

1. y = (x & 01010101) + ((x >> 1) & 01010101)
2. z = (y & 00110011) + ((y >> 10) & 00110011)
3. count = (z & 00001111) + ((z >> 1000) & 00001111)

···
···
···

获取32位二进制数内”1”个数

1. 每两位数存”1”的个数：
   storePer2 = (0x???????? & 0x55555555) + ((0x???????? >> 1) & 0x55555555)
2. 每四位数存”1”的个数：
   storePer4 = (storePer2 & 0x33333333) + ((storePer2 >> 2) & 0x33333333)
3. 每八位数存”1”的个数：
   storePer8 = (storePer4 & 0x0f0f0f0f) + ((storePer4 >> 4) & 0x0f0f0f0f)
4. 每十六位数存”1”的个数：
   storePer16 = (storePer8 & 0x00ff00ff) + ((storePer8 >> 8) & 0x00ff00ff)
5. 用32位数来存储结果：
   count = (storePer16 & 0x0000ffff) + ((storePer16 >> 16) & 0x0000ffff)

---

代码

/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */
#include <stdio.h>

int bitCount(int x)
{
	int tmpMask1 = (0x55) | (0x55 << 8);
	int mask1 = (tmpMask1) | (tmpMask1 << 16);
	int tmpMask2 = (0x33) | (0x33 << 8);
	int mask2 = (tmpMask2) | (tmpMask2 << 16);
	int tmpMask3 = (0x0f) | (0x0f << 8);
	int mask3 = (tmpMask3) | (tmpMask3 << 16);
	int mask4 = (0xff) | (0xff << 16);
	int mask5 = (0xff) | (0xff << 8);
	int count = x;
	count = (count & mask1) + ((count >> 1) & mask1);
	count = (count & mask2) + ((count >> 2) & mask2);
	count = (count & mask3) + ((count >> 4) & mask3);
	count = (count & mask4) + ((count >> 8) & mask4);
	count = (count & mask5) + ((count >> 16) & mask5);
	return count;
}

int main(void)
{
	printf("bitCount(5) = %d\nbitCount(7) = %d\n", bitCount(5), bitCount(7));
	return 0;
}

---