共计 2857 个字符，预计需要花费 8 分钟才能阅读完成。
题目：对于一个字节（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); }
