要进一家新公司难免要进行笔试，虽然笔试通过的人很多都有背题之嫌，但是统计意义上最起码可以看出一个程序员的认真程度，毕竟很多公司的考题也不是自己创的，也是在网上偷的，允许公司偷题就必须允许应聘者偷答案。短时间背下来答案并不难，难的是真正理解这些算法背后的思想，很多人在笔试期间可能一个也写不出来，但是只要写下来一些东西，很可能就被奇迹般录取了，应聘可不是高考，标准统一，有时一道笔试题你即使写不出来，但是让主审看出来你在使用一个小技巧，比如递归，那么他别的什么也不看就可能收你了。以下是我去年去一家公司应聘时的笔试题，当时我写下了以下的方法，语言是java：
int OneCount0(int i)
{
//将i转化为二进制字符串
String str = i + "";
//然后用StringBuffer类进行按顺序扫面，扫面字符'1'
}
然后又附上了以下三种方法，说实话OneCount0和OneCount1以及OneCount2是都是我自己想出来的，OneCount3是别人的，其实这不所谓自己的和别人的，只要你有计算机位运算的基础，OneCount1到OneCount3都是可以得到的，OneCount0是最笨的，我也不知道为何把这个笨方法作为了最终答案。答完之后考官问我为何如此写，我说没什么，就是要对待java公平一些，考官就是做java的，但是考官却认为我是故意戏弄他，当我将所有的题都答出并且多数答对之后，他又问我为何这么写，我就聊到了cpu的L1,L2的cache，聊到了堆栈，取指，指令流水线...我突然觉得我上当了，天真的我教会了考官那么多东西，天啊，我把那家公司拒了！这个考官简直什么也不懂，估计做java的大多都这样吧(但是真正的java高手同时也是c高手，不懂底层知识的占少数，只是国内真正的java高手太少了)，由于缺钱我应聘了一个比较简单的java职位，没有想到受到如此打击，欲哭无泪啊！我本将心向明月，奈何明月照沟渠！
unsigned int OneCount1( unsigned int i )
{
unsigned int count = 0;
unsigned int onetwo;
do
{
onetwo = i%2;
i = i/2; //i = i>>1;
count += onetwo?1:0;
}while ( i != 0 );
return count;
}
这个算法是显而易见的，其实就是将十进制转换为二进制的算法，转换过程中肯定对一个数字是1还是0是再清晰不过的，所以顺便可以完成统计1的个数的需求，但是效率呢？很差，为何差呢？很多人都知道这个算法的效率很差，原因是用到了循环，用到了除法等等，其实不必这么定量分析，想想它完成的功能吧，本质来讲，统计1的数目就是一个捎带的过程，从该算法的副作用上讲，它的效率并不算差，如果有硬件帮忙，它实际上是将十进制的数字转换成了二进制的表示方法，而不仅仅是统计了1的数目。
unsigned OneCount2(unsigned int i)
{
int j = 0;
while(x)
{
i = i&(i-1);
j ++;
}
return j;
}
该算法的效率比OneCount1高了不少，因为它去除了不必要的转换表示法的操作，仅仅就是统计了1的数目，一个&操作将努力使数据的高位清除，因为该算法是收敛的，努力使自己没有事情要做，因此onetwo = i%2之类的就没有了，onetwo?1:0;之类的判断赋值也没有了，直接一个位运算除了统计了1的数目之外再没有别的用处，每次x和x-1的与运算可以将为0的位的数量增加1，比如数字421的二进制为110100101，420的二进制为110100100，最低位的1被抹去了，二者按位相与之后，最低的两位都成了0，然后结果减1的二进制是110100011，最低位开始第三位为1，以此类推，总之只要减1，那么从低位到高位一直到为1的位，此位将变成0，而更低的位将全部变成1，二者按位与之后，这个递减之前的1被抹去，一直到结束。这个算法没有额外的作用，就数1的数量，效率较高。
unsigned long OneCount3(unsigned int x)
{
x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); //1
x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); //2
x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); //3
x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); //4
x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); //5
return x;
}
虽然OneCount2的效率较高，但是还是用到了判断，动态位运算，减法等等，即当前如何进行计算依赖于前一次计算的结果，这样在众多判断和动态运算机制之下，不利于利用cpu的硬件cache，如果能运用静态的表，或者说为了节省存储空间部分的使用静态表，然后剩下的部分用动态计算的方式，这就是第三种算法OneCount3.这个算法初看起来不是很好理解，但是比划几下似乎又不是很复杂，这个算法巧妙的地方在于一个个按位与最后将1的个数加到了一起，并且最终这个总合被移动到了最右边，本质上用到了递归的方式，只是没有用低效的基于栈的函数调用实现罢了。起初这个和是很多个，最终才被加到了一起，在相加的同时向右移动，递归结束的条件就是需要移位的宽度和x的宽度一致，第1行算出了16个和，分别记到了第0，2，4，...30位，必要的话进位到第1，3，5，...31位，比如第0位和第1位都是1，那么这两位1的个数就是2，结果就是10，可以看到占用了两位，其实仔细看一下仅这一步就将1的数量统计了出来，接下来就是将这16个加和加在一起就可以了，第2行的含义和第1行一样，就是将第1行加和的两位的结果再次加和，比如第0和第1位的加和为10，第2和第3位的加和为10，那么这四位的加和就是10+10=100，必要时进位到更高的位，但是进位不会超过两位，依次类推。
以上三种方式我在自己机器上进行了测试，用RDTSC指令测速，发现第三个算法最快，第一个最慢，但是如果我将三个算法放到一个程序中紧接着测试并且将OneCount1排到OneCount2和OneCount3之后运行却发现OneCount1是最快的，其实这是cpu缓存的作用，在OneCount2和OneCount3执行时已经在cache缓存了很多数据，等到OneCount1执行时就不用在访存了。
本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1274094
