旅途

如果想飞得高,就该把地平线忘掉

面试系列8--返回整数中为1的位数(优化版)

原题:

  Write the function int bitCount(short input) that takes a short as input and
  returns an int.  The function returns the number of bits set in the input
  variable.  For instance:
  bitCount(7) --> 3
  bitCount(2543) --> 9
  bitCount(11111) --> 9

  该题在《面试系列1...》中有解答,网友一修指出了答案的缺点,并给出了另外一个效率极高的算法,非常感谢,贴出来跟大家分享。 

/*
 * 平均效率比较低,最坏情况要循环sizeof(x) * 8次。
 * 看看下面这个函数,是针对32位的,至于其它位数稍加修改就可以了。
 *
 * return number of bits set
 */

unsigned int bitcount32(unsigned int x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
    // Version 1
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
    return x;
#else
    // Version 2
    x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
    x += x >> 8; // 0-16 in 8 bits
    x += x >> 16; // 0-32 in 8 bits
    return x & 0xff;
#endif
}

补充一下:

因为网友一修给出的代码中注释比较少,而精炼的代码又比较难理解,所以我来说说我的看法,如果有不对的地方,还请大家多多指导。

关于二进制数的理解,二进制数每一位只能为0和1,因此在这个地方,我们可以理解为每一位都可以表示该位中包含1的数目。

看第一行代码:x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);

5的二进制是 0101,当x & 0x55555555UL得出的结果是保留了0, 2, 4, 6 ... , 30 位的值,即 0, 2, 4, 6 ,... , 30 位中包含1的数目;那么自然可以理解(x >> 1) & 0x55555555UL得出的结果是保留了1, 3, 5, 7, ... , 31 位的值,即 1, 3, 5, 7, ..., 31 位中包含1的数目。把两者相加起来:

    xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx

  +0101 0101 0101 0101 0101 0101 0101 0101

------------------------------------------------------------------------

    0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x                            (这里的x即为x中 0, 2, 4, ... , 30 位的值)

 

    0xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx

  +0101 0101 0101 0101 0101 0101 0101 0101

------------------------------------------------------------------------

    0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y                            (这里的y即为x中 1, 3, 5 , ... , 31 位的值)

 

    0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x 0x0x

  +0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y 0y0y

------------------------------------------------------------------------

    zz zz zz zz zz zz zz zz

    可以把32位的X数每两位看成一个最小单元,x+y的值z即为这个两位最小单元中,1的个数。可以看出,巧妙地把两个加数种0的空间用来保存进位。那么到现在为止,我们就得到了数X中,每两位为最小单位,每两位中的数值表示着这两位中1的个数。

    依此类推,接下来我们用同样的方法计算以4位为最小单位,4位中的数值表示该4位中1的个数,即:x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);

    然后是 8位, 16位,当计算到以32位为最小单位,32位中的数值表示该32位中1的个数的时候,答案就揭晓了。

 

posted on 2007-09-05 01:17 旅途 阅读(154) 评论(0)  编辑 收藏 引用 所属分类: C/C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理