首页 > 代码库 > 菜鸟系列之C/C++经典试题(八)

菜鸟系列之C/C++经典试题(八)

计算二进制中1的个数

题目:位运算方面的编程很少遇到,但也是很重的一个只是点,一个比较常见的题目就是计算一个数的二进制表示中的1的个数。

分析:一个1都没有就是0, 我们的思路就是一位一位的运算, 我们很快就想到下面的做法:

int countBit1(int val)
{
    register int count = 0;
    while (val)
    {
        if (1 & val)
        {
            ++count;
        }
        val >>= 1;
    }

    return count;
}

砟一看这个实现不错, 仔细看看会有很大的问题, 就是当val是负数的时候,会出现死循环, 原因在于有符号进行的是算术位移, 会考虑到符号位的问题, 所以我们对此进行了修改, 换一种思路:

int countBit2(int val)
{
    register int count = 0;
    register unsigned int flag = 1;
    while (flag)
    {
        if (val & flag)
        {
            ++count;
        }
        flag <<= 1;
    }

    return count;
}

嗯, 这个实现解决了上面实现一种的无符号的问题, 但是有个缺点, 就是不管数中的1的个数有几个,都要循环32(sizeof(int) = 32的时候)这样不符合效率方面的要求, 所以仔细再看看实现一, 问题就是出现在有符号位移上, 我们看以强制把有符号转换成无符号在运算:

int countBit3(int val)
{
    register int count = 0;
    register unsigned int _val = val;
    while (_val)
    {
        if (1 & _val)
        {
            ++count;
        }
        _val >>= 1;
    }

    return count;
}

嗯, 干得不错, 这个实现算是可以得啦, 但是对于追求完美的程序员, 根本停不下来, 我们能不能有几个1就循环几次,而且, 循环体内有分支跳转, 这样会影响性能的,于是我进行思考:

例如: x = 1101的数, 我们进行如下运算:

x – 1 =1100, 细心的人会发现, 当最低位是1 的时候只改变最位, 当对位为0时候, 为1的最低位及左边的位取反, 因此我们能用n &= (n – 1)清楚右边的1。为什么n &= (n 1)能清除最右边的1呢?因为从二进制的角度讲,n相当于在n - 1的最低位加上1。举个例子,81000= 70111+ 10001),所以8 & 7 = 1000&0111= 00000),清除了8最右边的1(其实就是最高位的1,因为8的二进制中只有一个1)。再比如70111= 60110+ 10001),所以7 & 6 = 0111&0110= 60110),清除了7的二进制表示中最右边的1(也就是最低位的1

实现如下:

int countBit4(int val)
{
    register int count = 0;
    while (val)
    {
        ++count;
        val &= val - 1;
    }

    return count;
}
当然还有别的实现方法, 这里我就不列出来了。

如果有错误欢迎指出, 分享请辨明

感觉好的话就顶一个, 感觉不错的话就踩一个。

菜鸟系列之C/C++经典试题(八)