一、题目
求二进制中1的个数。对于一个字节（8bit）的无符号整型变量，求其二进制表示中"1"的个数，要求算法的执行效率尽可能的高。
二、解法
版本一（除法）：最简单的思路，利用求余算法统计1的个数。
TYPE count_number_1_in_byte(TYPE n)
{
TYPE sum = 0;
while(n) {
sum += n % 2 == 1 ? 1 : 0;
n /= 2;
}
return sum;
}
时间复杂度：O(lgn)
特点：根据二进制的规则，求余取得每一个位的值。由此可以延伸到多种进制求法，如八进制，十六进制，十进制，统计该表示下中各个位（八进制:0-7;十六进制:0-E;十进制:0-9）的数量。
版本二（移位）：计算机中采用二进制方式存储数据，可以利用位操作实现。
TYPE count_number_1_in_byte(TYPE n)
{
TYPE sum = 0;
while(n) {
sum += n & 0x01;
n >>= 1;
}
return sum;
}
时间复杂度：O(log2n)
特点：利用计算机中存储特性，把除2变为移位运算，提高运算效率。可以利用这个关系，在算法中实现2^n的倍数的乘除运算，如向左移2位表示该数乘以2^2=4。需要注意的是：右移运算需要保证该数为unsigned型（C/C++），保证无符号性提高程序可移植性。（这点在《C和指针》、《C陷阱与缺陷》中有提及。）拓展：求一个数的2的n次幂运算可以采用与操作符实现。
版本三（移位）：上一个版本采用位操作，但是操作的位数仍是八位。这个版本的算法在每次判断中，仅与1进行判断，利用的是特别的与运算n &= (n - 1)。
TYPE count_number_1_in_byte(TYPE n)
{
TYPE sum = 0;
while(n) {
n &= (n - 1);
sum++;
}
return sum;
}
时间复杂度：O(N)（N是n二进制表达中含1的位数个数，最差情况下是O(lgn)）
特点：采用了特定的位运算操作，这个思想来源于两个想法：判断一个数是否是2的某整数次幂可以利用判断语句if (n & (n-1) == 0)，同时使每次操作后的结果都减去一个1位直到最后的数变成0。
版本四（查表）:查表法，利用空间换取时间，罗列并直接给出值。(程序中也包含生成表的代码)
/**
* @file count_number_1_in_byte_v1.c
* @brief count the number 1 in binary form of a byte(8 bits).
* @author chenxilinsidney
* @version 1.0
* @date 2014-12-28
*/
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
typedef unsigned char TYPE;
TYPE N = 234;
TYPE search_list[UCHAR_MAX] = {0};
TYPE count_number_1_in_byte(TYPE n)
{
TYPE sum = 0;
while(n) {
n &= (n - 1);
sum++;
}
return sum;
}
int main(void)
{
/// 预先生成表
TYPE i = 0;
for (i = 0; i < UCHAR_MAX; i++)
search_list[i] = count_number_1_in_byte(i);
/// 查表法求值
TYPE sum = 0;
sum = search_list[N];
printf("sum of number 1 in %d is %d.\n", N, sum);
return EXIT_SUCCESS;
}
时间复杂度：O(1)
特点：利用了空间快速换取结果。书中提及重要的一点：在一个需要频繁使用这个算法的应用中，通过“空间换时间”来获取高的时间效率时一个常用的方法，具体的算法还应针对不同应用进行优化。
（这篇文章对查表法进行了另外一个方面的评价：http://blog.csdn.net/justpub/article/details/2292823
摘抄一：首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。
摘抄二：查表法看似一次地址计算就能解决，但实际上这里用到一个访存操作，而且第一次访存的时候很有可能那个数组不在cache里，这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle（因为要访问内存）。所以对于这种“小操作”，这个算法的性能其实是很差的。）
三、扩展问题
给定两个正整数A，B。判断A和B中有多少位是不同的？
方案：首先对A，B求异或，再利用上面版本三或版本四算法统计结果中“1”的位数，即可得到答案。
四、对题目深入学习
学习参考资料（使用了下面两种高级的算法）：
http://blog.csdn.net/justpub/article/details/2292823
http://blog.csdn.net/GSYzhu/article/details/8095174
http://blog.csdn.net/jiqiren007/article/details/6403133
http://blog.csdn.net/msquare/article/details/4536388
版本五（Hamming weight
认真阅读: http://en.wikipedia.org/wiki/Hamming_weight）:
在二进制表达中， 距离又称为：population count, popcount or sideways sum。算法实际上采用的是二分法，首先相邻的两位为一组各自相加统计各自两位上1的个数和，接下来相邻的四位为一组各自相加再统计各自四位上的个数和，如此下去到二进制左半位数和右半位数求和相加，得到的值和即为该数"1"的位数和。
时间复杂度：O(lgN)(这里N代表表示数据n的数据类型位数，此题中N
= 8)
特点：采用分治的思想，逐步缩小运算规模，求解问题的过程像是一棵倒置的二叉树。
算法实现（基本操作：shift and add，仅针对8位数据类型。针对更高字节数的数据类型，可以参考维基百科中的实现，并且维基百科还对它进行了进一步的优化，减少更多的运算操作）：
9 #include <stdlib.h>
10 #include <stdio.h>
11
12 typedef unsigned char TYPE;
13 TYPE N = 234;
14
15 TYPE count_number_1_in_byte(TYPE n)
16 {
17 n = (n & 0x55) + ((n >> 1) & 0x55);
18 n = (n & 0x33) + ((n >> 2) & 0x33);
19 n = (n & 0x0f) + ((n >> 4) & 0x0f);
20 return n;
21 }
22
23 int main(void)
24 {
25 TYPE sum = 0;
26 sum = count_number_1_in_byte(N);
27 printf("sum of number 1 in %d is %d.\n", N, sum);
28 return EXIT_SUCCESS;
29 }
下面代码片来自维基百科，通过对代码片分析和学习，进一步认识hamming weight 算法及其优化：
//types and constants used in the functions below
const uint64_t m1 = 0x5555555555555555; //binary: 0101...
const uint64_t m2 = 0x3333333333333333; //binary: 00110011..
const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; //binary: 4 zeros, 4 ones ...
const uint64_t m8 = 0x00ff00ff00ff00ff; //binary: 8 zeros, 8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t hff = 0xffffffffffffffff; //binary: all ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//It uses 24 arithmetic operations (shift, add, and).
int popcount_1(uint64_t x) {
x = (x & m1 ) + ((x >> 1) & m1 ); //put count of each 2 bits into those 2 bits
x = (x & m2 ) + ((x >> 2) & m2 ); //put count of each 4 bits into those 4 bits
x = (x & m4 ) + ((x >> 4) & m4 ); //put count of each 8 bits into those 8 bits
x = (x & m8 ) + ((x >> 8) & m8 ); //put count of each 16 bits into those 16 bits
x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits
return x;
}
//This uses fewer arithmetic operations than any other known
//implementation on machines with slow multiplication.
//It uses 17 arithmetic operations.
int popcount_2(uint64_t x) {
x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
x += x >> 8; //put count of each 16 bits into their lowest 8 bits
x += x >> 16; //put count of each 32 bits into their lowest 8 bits
x += x >> 32; //put count of each 64 bits into their lowest 8 bits
return x & 0x7f;
}
//This uses fewer arithmetic operations than any other known
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
int popcount_3(uint64_t x) {
x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
return (x * h01)>>56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
//This is better when most bits in x are 0
//It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.
int popcount_4(uint64_t x) {
int count;
for (count=0; x; count++)
x &= x-1;
return count;
}
static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
static int popcount(uint32_t i)
{
return (wordbits[i&0xFFFF] + wordbits[i>>16]);
}
代码片学习笔记:
popcount_1函数是最基本的实现，采用移位和求和两种操作实现8字节数据中“1”个数统计，用于理解算法分治的思想（分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。）。
popcount_2函数相比上一个函数实现减少了更多的操作步骤：
1.x = (x & m1) + ((x >> 1) & m1); 优化为： x -= (x >> 1) & m1; 这一步优化后少了一个与运算操作，它基于一个判定：ab - 0a = a + b，证明：当a = 0时,0b - 00 = 0 + b 等式成立，当a = 1时,若b = 0,10 - 01 = 1 + 0等式成立，若b
= 1,11 - 01 = 1 + 1 = 10等式也成立。
2.x = (x & m4) + ((x >> 4) & m4); 优化为：x = (x + (x >> 4)) & m4;这一步优化后少了一个与运算操作，原理是此时各自4位先求和（最大值为8）不会引起前面高4的位加一（需要和达到16），所以可以先求和再求与运算。而对于x
= (x & m2) + ((x >> 2) & m2);这一步不能实现相似的优化就是因为2位先求和（最大值为4时）会引起前面高2位加一（需要和达到4）导致计算错误。
3.x += x >> 8;x += x >> 16;x += x >> 32;x & 0x7f; 能够实现这一优化的原因是：对于8字节数据，“1”的个数最大位64，只需只用7个bit位就可以表示完全，各个位移后相加其他位情况不需考虑，并不会影响底7位的正确计数，最后只需与0x7f求与运算即可保留并得到正确的计数结果。
popcount_3函数相比上一个函数实现减少了更多的操作步骤，但是有一个高位乘法运算，因此适用于乘法运算速度较快的机器：
1.x += x >> 8;x += x >> 16;x += x >> 32;x & 0x7f;优化为：(x * h01)>>56;原理是：此步骤前x=0x0a0b0c0d0e0f0g0h(将每四个位求和的结果a,b,c,d,e,f,g,h表示为16进制形式)，x
* h01 = x * 0x01010101010101... = x * (0x0100000... + 0x0001.... + 0x000001... + .... + 0x01) = x * 0x01000.. + x * 0x0001... + ... + x * 0x01 = x << 56 + x << 48 + ... + x << 8 + x;此时最高的8位其值便是a + b + c + d + e + f + g + h，再右移56位即可得到正确的计数结果。
popcount_4函数与上述版本四一致，不过提供了一个重要的信息，对于一个大多数位都是零值的数来说，版本四的代码效率实际上会更高些。
popcount_5函数与上述版本五都采用了查表法的方法，却能够实现更多字节数数据类型的运算。值得学习的是它采用了分治的思想，把多字节数据数据类型，分解为各个小字节数据类型的组合（移位运算），再通过查表法统计求和。
版本六（HAKMEM）:这个方法从数学问题的角度出发去考虑，最后进行实现。
1.定义一个以n为底的多项式：P(k) = a0 * n^0 + a1 * n^1 + a2 * n^3 + ... + ak * n^k
定义对P(k)进行多项式消权后得到的结果为：S = a0 + a1 + a2 + ... + ak
若把这个想法和“求解二进制“1”的个数”这一个问题相结合，则我们考虑的问题中：P(k)是一个以2为底的多项式，a1 .. ak代表各个位上的数值，包括1和0两种，消权后的结果S即为问题的解：“1”的个数。
2.我们证明一个接下来要用到的等式：
对任何自然数n的N次幂，用n-1取模得数为1：(n^N) % (n - 1) = 1。
证明：若 (n^(k-1)) % (n-1) = 1 成立，则:
(n^k) % (n-1) = (n^k - n^(k-1) + n^(k-1)) % (n-1)
= ((n-1)*n^(k-1) + n^(k-1)) % (n-1)
= 0 + (n^(k-1)) % (n-1)
= 1 也成
又当k = 1 时：(n^(k - 1)) % (n-1) = (n^0) % (n-1) = 1
得证。
3.P(k) % (n-1)
= (a0 * n^0) % (n-1) + (a1 * n^1) % (n-1) +(a2 * n^0) % (n-1) + ... +(ak * n^k) % (n-1)
上面等式：若a0, a1, a2...ak 每个系数均小于n-1，则这些系数不会影响到求余运算，等式可以继续转化为：
P(k) % (n-1) = a0 * 1 + a1 * 1 + a2 * 1 + ... + ak * 1 =a0 + a1 + a2 + ... + ak
即对多项式完成了消权，并求得消权后系数的和。
进一步可推断，若(a0 + a1 + a2 + ... + ak) < (n - 1)，则上述式子必然成立。
4.在“求解二进制“1”的个数”这一个问题时，若利用计算机二进制表达方式，我们的多项式以2为底，n = 2，显然上式中(a0
+ a1 + a2 + ... + ak) < (n - 1) 无法满足条件（针对所有情况）。但是，如果我们的多项式不以2为底，而换成更大的数，满足条件时有可能的。对于32位整数（4字节）来说，(a0 + a1 + a2 + .. + ak) <= 32 ，故取n > 33 便可以满足条件。考虑到计算机二进制移位运算效率比乘除运算效率高这个特点，同时针对实现多个位求“1”个数这个问题，我们可以取n = 2^6 = 64.
5.要应用上面这个思路，我们必须对下面初始的二进制表式先进行转化：
P(k) = a0 * 2^0 + a1 *
2^1 + a2 * 2^3 + ... + ak * 2^k (n = 2)
我们针对32位整数着一个情况，我们可以把它转化为：
P(k)
= b0 * 64^0 + b1 * 64^1 + b2 * 64^3 + ... + bk * 64^k (n = 64)
这样我们再对转换后的多项式进行求模运算，即可得到：
P(k)
% (64 - 1) = b0 + b1 + b2 + .. + bk(n
= 64)
那么，此时a0,a1,a2
... ak 和b0,b1,b2 ... bk之间的关系是什么呢？因为我们的问题是求解二进制数中“1”的个数，所以a1 .. ak代表各个位上的数值，包括1和0两种，为了使b0 + b1 + b2 + ... + bk这个值的结果也表示为二进制数中“1”的个数，我们可以对a1
... a6 这6个位求和得到b0，对a7 ... a12这6个位求和得到b1，(有：n = 2^6 = 64)，如此下去，那么最后的表达式P(k)
% (64 - 1) 就是问题的解：二进制数中“1”的个数!
具体实现如下：对于六位二进制数ti（n = 2），转换为b（n = 64）
b = (ti>>5)&(000001) + (ti&>>4)(000001) + (ti>>3)&(000001) + (ti>>2)&(000001)
+ (ti>>1)&(000001) + ti&(000001)
算法实现：通过以上分析，我们可以得到32位整型数据的初级版的HAKMEM的算法:
9 #include <stdlib.h>
10 #include <stdio.h>
11
12 typedef unsigned int TYPE;
13 TYPE N = 234;
14
15 TYPE count_number_1_in_byte(TYPE n)
16 {
17 TYPE m1 = 0x41041041;
18 n = (n & m1) +
19 ((n >> 1) & m1) +
20 ((n >> 2) & m1) +
21 ((n >> 3) & m1) +
22 ((n >> 4) & m1) +
23 ((n >> 5) & m1);
24 return n % 63;
25 }
26
27 int main(void)
28 {
29 TYPE sum = 0;
30 sum = count_number_1_in_byte(N);
31 printf("sum of number 1 in %d is %d.\n", N, sum);
32 return EXIT_SUCCESS;
33 }
（解释下m1 = 0x41041041，这个值是十六进制从低位开始每6个位置000001得到的，因为是6个位求和，但为了更好的表示含义可以修改为8进制数（每3个二进制位求和），即m1 = 010101010101(C语言0开头的常数为8进制数)，后面的算法均采用八进制表达）
优化一：对于6位二进制数来说，“1”个数最大值为6，仅需占用3位便可以表达最大值(二进制数110)。因此，可以采用分治的思想，把6位二进制数二分，对每三位求“1”的个数和，再利用移位求和得到6位二进制“1”的个数和。由此得到优化后的算法：
9 #include <stdlib.h>
10 #include <stdio.h>
11
12 typedef unsigned int TYPE;
13 TYPE N = 234;
14
15 TYPE count_number_1_in_byte(TYPE n)
16 {
17 n = (n & 011111111111) +
18 ((n >> 1) & 011111111111) +
19 ((n >> 2) & 011111111111);
20 n = (n + (n >> 3)) & 030707070707;
21 return n % 63;
22 }
23
24 int main(void)
25 {
26 TYPE sum = 0;
27 sum = count_number_1_in_byte(N);
28 printf("sum of number 1 in %d is %d.\n", N, sum);
29 return EXIT_SUCCESS;
30 }
（注意上一个版本中的常数为：010101010101（6位求和），这个版本中变化为变化为011111111111（3位求和））
优化二：下面的优化减少了更多的操作数，基于这一个原理：对于3位的二进制数4a+2b+c来说，我们求解的是a
+ b + c，可以通过以下等式求解，a + b + c = (4a + 2b + c) - (2a + b) - a，这里(4a + 2b + c)表示原始的3位二进制数，(2a + b)表示原始的3位二进制数右移一位的结果，a表示原始的3位二进制数右移两位的结果。利用这个等式可以简化运算步骤，得出以下的算法：
9 #include <stdlib.h>
10 #include <stdio.h>
11
12 typedef unsigned int TYPE;
13 TYPE N = 234;
14
15 TYPE count_number_1_in_byte(TYPE n)
16 {
17 n = n - ((n >> 1) & 033333333333) -
18 ((n >> 2) & 011111111111);
19 n = (n + (n >> 3)) & 030707070707;
20 return n % 63;
21 }
22
23 int main(void)
24 {
25 TYPE sum = 0;
26 sum = count_number_1_in_byte(N);
27 printf("sum of number 1 in %d is %d.\n", N, sum);
28 return EXIT_SUCCESS;
29 }