题目：对于一个字节（8bit）的变量，求其二进制“1”的个数。例如6（二进制0000 0110）“1”的个数为2，要求算法效率尽量高。
解法一：除法
对于二进制数来说，除一个2，就少一位，能够判断这个少的位来确定“1”的个数。
例如：6（0000 0110）
0000 0110 / 2 = 0000 0011 ----少的一位为0
0000 0011 / 2 = 0000 0001 ----少的一位为1
0000 0001 / 2 = 0000 0000 ----少的一位为1
操作数数曾经为0，到此结束
参考代码
int Count_1(int val){ int num = 0; while(val) { if(val % 2 != 0) //用取模取得去除的一位 ++num; val /= 2; } return num;}性能：工夫复杂度O(log2v)，即二进制数的位数；空间复杂度O(1)
解法二：移位
对于二进制数来说，除法是用移位实现。
例如：6（0000 0110）
0000 0110 >> 1 = 0000 0011 ----少的一位为0
0000 0011 >> 1 = 0000 0001 ----少的一位为1
0000 0001 >> 1 = 0000 0000 ----少的一位为1
操作数数曾经为0，到此结束
参考代码
int Count_2(int val){ int num = 0; while(val) { if(val & 1 != 0) //用与1与取得移除的一位 ++num; val >>= 1; } return num;}性能：工夫复杂度O(log2v)，即二进制数的位数；空间复杂度O(1)
解法三：高效移位
对于上述算法，有个问题，比方1000 0000，大把的工夫用在没用的0上，最好寻求一种直接判断“1的个数。
通过观察能够找到法则：对于数a, a = a & (a-1)就能够去除a的最初一个1
例如：6（0000 0110）
0000 0110 & 0000 0101 = 0000 0100
0000 0100 & 0000 0011 = 0000 0000
操作数数曾经为0，到此结束
参考代码
int Count_3(int val){ int num = 0; while(val) { val &= (val -1); ++num; } return num;}性能：工夫复杂度O(M)，即二进制中“1”的个数，空间复杂度O(1)
解法四：查表
查表法，把0~255这256个数的后果全副存储在数组中，val间接作为下标，countTable[val]即为后果。典型的用空间换工夫。
参考代码
int Count_5(int val){ int countTable[] = {0, 1, 1, 2, 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, 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, 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}; return countTable[val];}性能：工夫复杂度：O(1), 空间复杂度O(N)
整个程序执行参考
#include<iostream>using namespace std;int Count_1(int val){ int num = 0; while(val) { if(val % 2 != 0) ++num; val /= 2; } return num;}int Count_2(int val){ int num = 0; while(val) { if(val & 1 != 0) ++num; val >>= 1; } return num;}int Count_3(int val){ int num = 0; while(val) { val &= (val -1); ++num; } return num;}int Count_5(int val){ int countTable[] = {0, 1, 1, 2, 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, 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, 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}; return countTable[val];}int main(){ int a = 6, b = 255; cout << "Num of 1:" << Count_1(a) << endl; cout << "Num of 1:" << Count_2(a) << endl; cout << "Num of 1:" << Count_3(a) << endl; cout << "Num of 1:" << Count_5(b) << endl; cout << "Num of 1:" << Count_1(b) << endl; cout << "Num of 1:" << Count_2(b) << endl; cout << "Num of 1:" << Count_3(b) << endl; cout << "Num of 1:" << Count_5(b) << endl; }扩大问题：异或后转化为该问题
- 给定两个正整数（二进制示意）A、B，如何疾速找出A和B二进制示意中不同位数的个数。
思路
首先A和B进行异或操作，而后求得到的后果中1的个数（此问题）。
判断一个数是否是2的幂
bool powerof2(int n){ return ((n & (n-1)) == 0);}