求二进制数中1的个数

Posted on | In | |
Words count in article: 591 | Reading time ≈ 2

求二进制数中1的个数

对于一个字节（8bit）的无符号整型变量，求其二进制表示中‘1’的个数，要求算法执行的效率尽可能高

解法一：

利用整型数据除法的特点，通过相除和判断余数的值来分析

1
2
3
4
5
6
7
8
9
10
11
12
13
int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        if(v%2 == 1)
        {
            num++;
        }
        v /= 2;
    }
    return num;
}

解法二：使用位操作

向右移位操作同样可以达到相除的目的，唯一的不同之处在于，移位之后如何来判断是否有1存在。

需要判断最后一位是否为1，“与”操作可以达到目的，可以把该数与00000001进行与操作，如果结果为1，则表示当前八位数的最后一位为1，否则为0.

1
2
3
4
5
6
7
8
9
10
int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        num += v & 0x01;
        v >>= 1;
    }
    return num;
}

解法三：

位操作比除、余操作的效率高了很多，但是，即使使用位操作，时间复杂度仍然为O(log2v)

能否将复杂度进一步降低？

为了简化这个问题，我们考虑只有一个1的情况，例如：01000000

如何判断给定的二进制数只有一个1呢？可以通过判断这个数是否为2的整数次幂来实现。另外，如果只和这个1进行判断，如果希望操作后的结果为0，01000000可以和00111111来进行与操作。

这样，要进行的操作就是0100000 & （01000000 - 00000001） = 01000000 & 00111111 = 0

将这种判断只有一个1的做法推广到有不确定1的情况即有如下代码：

1
2
3
4
5
6
7
8
9
10
int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        v &= (v-1);
        num++;
    }
    return num;
}

解法四：

解法三的复杂度已经降低到O(M)，M为v中1的个数

若想继续降低时间复杂度，还可以利用空间换时间，提前制好8bit二进制数（255个）各自对应的num的一个数组（表），然后进行查表操作，无需进行任何比较。

相关问题：

给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A和B的二进制表示中有多少位是不同的？

与非 -> 求有多少个1

Donate? comment?