今天公司和公司同事一起讨论五子棋的时候，他给我说了他的算法
这里五子棋的算法就不说啦
不过其实他的本质：
就是计算无符号整数中二进制中1的个数的思想
对此我也记录一下
1 //获取正整数十进制的二进制数表示法
2 int get2(unsigned int n)
3 {
4 int nNum = 0; //保存最后的数（10进制数，2进制格式）
5 bool bDouble = false; //是否是双数
6 if(n%2 == 0)
7 {
8 nNum = 1;
9 bDouble = true;
10 }
11 for(; n > 0;n >>= 1)
12 {
13 nNum*=10;
14 nNum+=( n & 1 );
15 }
16 if(bDouble)
17 {
18 nNum -= 1;
19 nNum /= 10;
20 }
21 return nNum;
22 }
23 int main()
24 {
25 cout << get2(257);
26 getchar();
27 return 0;
28 }
就是将十进制的数以二进制的格式保存（强调“格式”两个字！）
1 //求正整数二进制中1的个数
2 int getoneNum(unsigned int n)
3 {
4 int i = 0;
5 for(; n > 0;n >>= 1)
6 {
7 i+=( n & 1 );
8 }
9 return i;
10 }
11 //测试输出
12 int main()
13 {
14 cout << getoneNum(253);
15 getchar();
16 return 0;
17 }
这样的时间复杂度是T(m)=m，取决于二进制数的位数m。如果要求在更短时间内求出，应该如何做呢？
其实大家都喜欢用的方法就是查表法，以空间换取时间。预先把结果存入表中（怎么存就自己写了呗~想一个一个算也是OK的，没有做不到，只有想不到），
然后直接通过下标就可以访问了。
1 static char tOne[256] = {
2 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,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,
4 3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,
5 3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,
6 3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,
7 5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,
8 3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,
9 4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,
10 3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,
11 5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,
12 5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,1
13 };
14 int GetOneByArray(unsigned int n)
15 {
16 n -= 1;
17 int i;
18 for(i = 0;n > 0;n>>=8)
19 {
20 i += tOne[n&255];
21 }
22 return i;
23 }
24 int main()
25 {
26 cout << GetOneByArray(255);
27 getchar();
28 return 0;
29 }
这样的话，就可以直接读取1-256中1的个数了。在速度上达到的优化，通过tOne[x]就可以得到，连判断都可以不用，速度大大提升。
然后一个整型有4个字节，32位。1-256远远不够，难道要用1-2的32次方的表来保存？还是那句话，没有做不到，只有想不到。
OK，算一下如果要保存2的32次方个数的1的个数，那么这个数组的大小
至少2^32/(256/32)=512MB，哈哈，正是一般内存大小，搞定速度优化，应该还需要内存优化吧。空间换取时间也不能这么高的空间代价吧
于是需要再优化：存放1-256每个数中1的个数，然后分段查询。如上面把32位数分为4段，每段一个字节，所以有一个256大小供查询的表，比512M小太多了吧。
这样就能完成每个int数中二进制1的个数的查询了，站在巨人的肩上学习真好。
话说回来，我同事也用了这种有限的查表法来查询五子棋中某个下子点周围40个空格(当然，一般都小于40个）的状态变化，而状态就是一张表，其实也不多，数据量
比这个要大一些，不过写完的状态大概也只有几十K罢了，我还是喜欢先速度优化再内存优化的方式，因为这样可以让我最大限度的找到我个人认为比较综合有效的解决
方案。