求二进制数中1的个数

对于一个32位的无符号整型变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能高。

#include <stdio.h>  
  
/* 求余和相除相结合的方法 */  
int Count1(int v)  
{  
    int num = 0;  
    while(v)  
    {  
        if(v%2 == 1)  
        {  
            num++;  
        }  
        v /=2;  
    }  
    return num;  
}  
  
/* 位移操作代替除、余操作 */  
int Count2(int v)  
{  
    int num = 0;  
    while(v)  
    {  
        if(v&0x01)  
        {  
            num++;  
        }  
        v >>= 1;  //右移一位相当于除以2  
    }  
    return num;  
}  
  
/* 自身减一后进行按位与操作 */  
int Count3(int v)  
{  
    int num = 0;  
    while(v)  
    {  
        v &=(v-1);  
        num++;  
    }  
    return num;  
}  
  
int main(void)  
{  
    int a;  
    printf("请输入1个32位的整数：");  
    scanf("%d",&a);  
    printf("二进制中1的个数为：%d,%d,%d\n",Count1(a),Count2(a),Count3(a));  
    return 0;  
}

执行结果：

解法1和解法2的时间复杂度都是O(log2v)，解法3的时间复杂度是O(v)

那有没有时间复杂度是O（1）的呢？答案是有的，但是这种是用空间换时间的方法。

方法4：使用switch case语句，数字越小效率越高，数字越大比较的次数越多效率越低。

方法5：预定义的结果表，将一个整数，这里拿1个字节的整数来说，比如数字是在0~255，那么定义一个256大小的数组，直接在数组设定好0~255对应二进制1的个数。

这二种方法的时间复杂度都是O（1），但这是用空间换时间的办法，在嵌入式编程中，不推荐。这里推荐使用方法3.

补充：软件开发 , C++ ,