一道笔试题--求二进制数1的个数

晨曦之光 发布于 2012/04/10 15:03
阅读 361
收藏 1

要进一家新公司难免要进行笔试,虽然笔试通过的人很多都有背题之嫌,但是统计意义上最起码可以看出一个程序员的认真程度,毕竟很多公司的考题也不是自己创的,也是在网上偷的,允许公司偷题就必须允许应聘者偷答案。短时间背下来答案并不难,难的是真正理解这些算法背后的思想,很多人在笔试期间可能一个也写不出来,但是只要写下来一些东西,很可能就被奇迹般录取了,应聘可不是高考,标准统一,有时一道笔试题你即使写不出来,但是让主审看出来你在使用一个小技巧,比如递归,那么他别的什么也不看就可能收你了。以下是我去年去一家公司应聘时的笔试题,当时我写下了以下的方法,语言是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执行时就不用在访存了。


原文链接:http://blog.csdn.net/dog250/article/details/5302953
加载中
0
t
ts32767

笨人的笨办法,移位加一。(顺便说一句,其实面试也是一种交流,无所谓把自己学的告诉别人,都是工程师嘛)

int countOne4(long a){

int j=0;

 for(int i=0;i<8*sizeof(a);i++)
          j+=(a&0x01>0)?1:0;

return j;

}

测试过的代码:

#include <iostream>

using namespace std;
using std::hex;
using std::dec;

int main()
{
    long a=1;
    int j=0;
    while(a)
    {
        cout<<"Please Input a Number:";
        cin>>a;
        for(int i=0;i<8*sizeof(a);i++)
          j+=(a&0x01>0)?1:0;
        cout<<endl<<"Number of [0x"<<hex<<a<<dec<<"] contains bit vale '1' is :"<<j<<endl<<endl;
        j=0;
    }
     return 0;
}

返回顶部
顶部