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

最后更新于:2022-04-01 16:17:11

# 一、可能死循环的方法 给出通常能想到的方式,这两种方式在《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而陷入死循环。参考文章[位运算的常见操作和题目](http://blog.csdn.net/u013074465/article/details/46686881) # 二、避免死循环的方法 为了避免死循环,不右移数字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的个数少一个。 **![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-06-07_575683a3eb371.jpg)** ### **2、位移方法** **参考文章:[](#)[二进制位的翻转和二进制表示中1的个数](http://blog.csdn.net/u013074465/article/details/45485959)**
';