工学1号馆

home

« | 返回首页 | »

求二进制数中1的个数

By Wu Yudong on July 24, 2016

实现一个函数,输入一个无符号整数,输出该数二进制中的1的个数。例如把9表示成二进制是1001,有2位是1,因此如果输入9,该函数输出2

解法1:利用十进制和二进制相互转化的规则,依次除余操作的结果是否为1  代码如下:

int Count1(unsigned int v)
{
    int num = 0;
    while (v) {
        if (v % 2 == 1) {
            num++;
        }
        v = v / 2;
    }
    return num;
}

解法2:向右移位操作同样可以达到相同的目的,唯一不同的是,移位之后如何来判断是否有1存在。对于这个问题,举例:10100001,在向右移位的过程中,我们会把最后一位丢弃,因此需要判断最后一位是否为1,这个需要与00000001进行位“与”操作,看结果是否为1,如果为1,则表示当前最后八位最后一位为1,否则为0,算法时间复杂度为O(log2v)。代码实现如下:

int Count2(unsigned int v)
{
    unsigned int num = 0;
    while (v) {
        num += v & 0x01;
        v >>= 1;
    }
    return num;
}

解法3:利用"与"操作,不断清除n的二进制表示中最右边的1,同时累加计数器,直至n为0,这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有M个1,那么这个方法只需要循环k次即可,所以其时间复杂度O(M),代码实现如下:

int Count3(unsigned int v)
{
    int num = 0;
    while (v) {
        v &= (v - 1);
        num++;
    }
    return num;
}

解法4:既然题目是一个无符号整数,只有8位数据,索性直接把0~255的情况直接都罗列出来,并使用分支操作,代码如下:

int Count4(unsigned int v)
{
    int num = 0;
    switch (v) {
    case 0x0:
        num = 0;
        break;
    case 0x1:
    case 0x2:
    case 0x4:
    case 0x8:
    case 0x10:
    case 0x20:
    case 0x40:
    case 0x80:
        num = 1;
        break;
    case 0x3:
    case 0x6:
    case 0xc:
    case 0x18:
    case 0x30:
    case 0x60:
    case 0xc0:
        num = 2;
        break;
    //...
    }
    return num;
}

解法5:查表法空间换时间

把0~255中“1”的个数直接存储在数组中,v作为数组下标,countTable[v]就是v中“1”的个数。算法时间复杂度仅为O(1),代码如下:
int countTable[256] = {
    0, 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, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
int Count5(BYTE v)
{
    return countTbale[v];
}

 

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)