求二进制数中1的个数（编程之美）

刺骨的言语ヽ痛彻心扉 2022-08-06 12:09 268阅读 0赞

**求二进制数中1的个数**

题目描述：对于一个字节1BYTE = 8 bits的无符号变量，求其二进制表示中1的个数，要求算法的执行效率尽可能高。

题目分析：可以吧这个问题转化为判断这个数的最后1位数是否等于1，然后逐渐往右移位，不断判断下去，直到该数为零。

按照这种分析，那么就有两部分需要做：

1）判断最后一位是否为零；

2）如果右移位。

这样就有三种思路。

思路一：1）可以通过除以2，看余数是否等于0/1实现；2）可以通过除以2；

思路二：1）可以通过和0x01按位与，如果结果为1就表示最后一位为1，否则就是0；2）可以右移位实现除以2；

思路三：1）可以通过v & (v-1)来实现，充分利用了相邻数最后一个二进制位相异的特点；2）同思路2.

代码如下：

// 思路2

#include<iostream>
    typedef unsigned char BYTE;  //BYTE类型在C++中是没有的，其实它就是无符号字符型，人们一般关注它的长度，而不是类型
    using namespace std; 
    
    int count(BYTE v)
    {
    	int num = 0; 
    	while(v)
    	{
    		num += v&0x01;   //按位与
    		v >>= 1;   //右移位
    	}
    	return num; 
    }
    
    int main()
    {
    	BYTE x = 255;   //BYTE类型只有8bits, 所以最大只能是255, 0-255
    	cout<<count(x)<<endl;  //输入1的个数
    
    	return 0; 
    }

其中的注释帮助理解BYTE类型。

// 思路3

#include<iostream>
    typedef unsigned char BYTE; 
    using namespace std; 
    
    int count(BYTE v)
    {
    	int num = 0; 
    	while(v)
    	{
    		//num += v&0x01; 
    		//v >>= 1; 
    
    		v &= (v-1); 
    		num++; 
    	}
    	return num; 
    }
    
    int main()
    {
    	BYTE x = 255; 
    	cout<<count(x)<<endl; 
    
    	return 0; 
    }

可以看出 v &= (v-1); 这样子做就可以省去了右移位的操作，这样更加简单。

时间复杂度方面：

思路2，时间复杂度和v的二进制位数有关，而一个数的二进制的位数为logv,故O(logv);

思路3，直接和v中1的个数有关，是O(M).

思路1的和思路2的一样，不过做法比思路2要大，因为位操作比除法和余法要效率来的高~

参考：

关于BYTE：

http://bbs.csdn.net/topics/310267652

http://www.cxybl.com/html/bcyy/c/201109073136.html

《编程之美》