题目地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=222
思路来源:http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
思路: 题目中的a,b为32位非负，因此可用unsigned int表示。即32位二进制。32位二进制可看作四个字节，即四个8位数组成，见下图:
而8位二进制数可表示范围为0到2^8 - 1， 即0~255 因此我们可以设置一个大小为256的表，用来存放0~255各数的二进制形式中1的个数 对于二进制数中1的个数可推导出以下规则: 1.对于偶数n，其二进制形式中1的个数与n/2的二进制形式中1的个数相等。因为在偶数的二进制形式中，最低位为0，而n/2相当于将n右移一位，1的个数不会受到影响。 2.对于奇数n，其二进制形式中1的个数等于n/2的二进制形式中1的个数再加1.因为奇数的二进制形式中最低位为1，同理，转换为n/2的右移过程中将损失最低位的1. 通过以上两条规则可获得如下建表算法: unsigned char countTable[256] = {0}; void initTable() { for (unsigned int i=0; i<256; i++) { countTable[i] = (i & 1) + countTable[i/2]; } } 有了这个表之后，对任何一个8位二进制数，我们可以直接从表中取出其二进制形式中1的个数。 如要知道100的二进制形式中有多少个1，直接取countTable[100]即可 那么如何将32位整数转换为4个8位整数呢，这里就要用到C语言中指针的特性。 对Int类型指针，每次指针加1地址向前移动4个字节 对char类型指针， 每次指针加1地址向前移动1个字节 若我们将一个int变量的地址赋给一个char型指针p，则可分别通过p[0], p[1], p[2], p[3]拿到该int变量的4部分8位形式。原理如下: 综合以上思路，对于任何一个32位数n，只需用一个char类型指针p指向，然后通过countTable[p[0]] + countTable[p[1]] + countTable[p[2]] + countTable[p[3]]即可获得n二进制形式中1的总数。整个算法耗时O(n) 最终代码: #include <stdio.h> unsigned char countTable[256] = {0}; void initTable() { for (unsigned int i=0; i<256; i++) { countTable[i] = (i & 1) + countTable[i/2]; } } int main(void) { initTable(); unsigned int a, b; unsigned char* p; unsigned int count = 0; scanf("%d%d", &a, &b); for (unsigned int i=a; i<=b; i++) { p = (unsigned char*)&i; count += countTable[p[0]] + countTable[p[1]] + countTable[p[2]] + countTable[p[3]]; } printf("%d\n", count); }
