整数的二进制表示中1的个数

谁践踏了优雅 2022-08-06 09:30 182阅读 0赞

# 一、可能死循环的方法 #

给出通常能想到的方式，这两种方式在《C和指针》一书中给出。*以下讨论的均为非负整数。*

/*
    该方法每次在循环中判断数的二进制最右一位是否为1（如果该数能不能被2整除）。
    每次循环后该数右移一位。因此遍历了数的二进制表示的每一位。
    */
    int count_one_bits1(int value) {
    	int count;
    	for (count = 0; value != 0; value >>= 1)
    		if (value % 2 != 0)
    			count++;
    	return count;
    }
    
    /*
    与上边方法类似，也是每次将该数右移一位，遍历该数的二进制表示的每一位。
    不过这里是将该数与1做与运算，这样，与的结果不为零则说明该数的二进制表示的最右一位为1。
    */
    int count_one_bits2(int value) {
    	int count;
    	for (count = 0; value != 0; value >>= 1) {
    		if ((value & 1) != 0)
    			count++;
    	}
    	return count;
    }
    
    //这里只是上述方法的另外一种写法
    int count_one_bits3(int value) {
    	int count = 0;
    	while (value) {
    		if (value & 1)
    			++count;
    		value >>= 1;
    	}
    	return count;
    }

以上给出的方法**当数为负数的时候会死循环**。因为计算机中数是用二进制补码表示的，负数右移其最高位补1（算术右移），那么如上的方法，会一直右移，不断在最高位补1，最终数字变为0xffffffff而陷入死循环。参考文章[位运算的常见操作和题目][Link 1]

# 二、避免死循环的方法 #

为了避免死循环，不右移数字value，而是现将value和1做与运算，判断最低位是否为1；接着把1做移一位得到2，再和value与运算，判断value的次低位是否为1；依次下去……判断value的每一位是否为1。 **32位整数要循环32次**。

int count_one_bits4(int value) {
    	int count = 0;
    	unsigned int flag = 1; //这里将flag设为无符号整型很重要
    	while (flag) {
    		if (value & flag)
    			++count;
    		flag = flag << 1;
    	}
    	return count;
    }

# 三、高效方法 #

## 1、循环方法 ##

下面介绍另外一种方式，可以通过比上述少的比较次数来统计出数的二进制表示中1的个数。

首先作如下分析：

n & (n - 1)可以将n的二进制表示中最右侧的一个1去掉，例如1100 减去1得到1011，那么 1100 & 1011得到1000，即将1100最右侧的一个1去掉。如下函数每次循环就去掉其二进制表示中一个1，那么**函数循环的次数就是其二进制表示中所含1的个数**。

int count_one_bits3(int value) {
    	int count = 0;
    	while (value) {
    		++count;
    		value = value & (value - 1);
    		//int v1 = value;
    		//cout << value << " ";
    	}
    	cout << endl;
    	return count;
    }

while循环结束的条件是value为0，也就是当value是2的n次幂时，下一次循环就结束了，因为2的n次幂的二进制表示中仅含有一个1。循环中value = value & (value - 1)使得每次循环后，value的二进制表示中1的个数少一个。该方法与前两个方法比，循环的次数少。

如下图，输入value为8888，可以看出方法1执行while循环14次，方法3执行while循环6次。方法3每次循环后value的二进制中1的个数少一个。

**![Center][]**

## **2、位移方法** ##

**参考文章：[二进制位的翻转和二进制表示中1的个数][1]**

[Link 1]: http://blog.csdn.net/u013074465/article/details/46686881
[Center]: /images/20220806/3c01db0af6d144849ecf92ea45ffabc6.png
[1]: http://blog.csdn.net/u013074465/article/details/45485959