关于统计整数转换为二进制后含多少1的问题

之前看剑指offer时候遇到这个问题，对书中最后提出的算法很是惊艳，然后去网上查找了一番，总结了一下整数转换为二进制以后含有多少1的问题的4种方法：
1、最常规的方法
思路：先判断整数最右边一位是否为1，接着把输入的整数右移一位，此时原来处于从右边数起的第二位被移到最右边了，再判断是不是1。这样反复进行，知道整数变为0。
代码：

int NumberOf1(int n){
  int count = 0;
  while(n){
  if(n & 1)
    count ++;
  n = n >> 1;
}
return count;
}

但是这种方法如果输入为一个负数的时候，如果一直做右移运算，最终这个数字会变成0xFFFFFFFF，从而陷入死循环。

二、变换上面的方法，将与整数n做&运算的1左移
代码

int NumberOf1(int n){
  int count = 0;
  unsigned int flag = 1;
  while(flag){
  if(n & flag)
    count ++;
  flag = flag << 1;
}
return count;
}

三、这是剑指offer提出的能给面试官带来惊喜的解法
总结一下一个：
规律1：把一个整数减去1，都是把最右边的1变为0，如果他的右边还有0的话，所有的0全部都变成1，而它左边所有位都保持不变。例如0100减1之后变为0011。
规律2：把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。
基于规律2，可以写出统计整数二进制中多少个1的代码：

int NumberOf1(int n){
  int count = 0;
  unsigned int flag = 1;
  while(n){
    count ++;
    n = (n - 1) & n;
}
return count;
}

很惊喜找到了这样3种方法来统计整数二进制中1的个数，但是，当我在leetcode上看到题目binary watch时，尝试用第三种方式统计出时钟中亮的LED和分钟中亮的LED时，发现用这种方法超时了。。。
于是，去网上搜了一下，然后更惊艳的关于统计整数二进制中1的个数的方法出现了：
借助C++中专门处理二进制数的类bitset
相关的头文件：

#include <bitset>  
using std::bitset; 

初始化

bitset<n> b;            //b有n位，每位都为0  
bitset<n> b(u);             //b是unsigned long型u的一个副本  
bitset<n> b(s);             //b是string对象s中含有的位串的副本  
bitset<n> b(s, pos, n);     //b是s中从位置pos开始的n个位的副本 

类似于vector，bitset类是一种类模板；而与vector不一样的是bitset类型对象的区别仅在其长度而不在其类型。在定义bitset时，要明确bitset含有多少位，须在尖括号内给出它的长度值：

bitset<32> bitvec; //32位，全为0。

也可以用字符串初始化：

string str = "1111111000000011001101";  
bitset<32> bitvec4(str);
bitset<32> bitvec5(str, 5, 4); //从第5个字符开始的连续4个
bitset<32> bitvec6(str, str.size() - 4);// 倒数第四个开始到末尾

bitset上的操作

我们发现，bitset类中含有直接统计二进制整数中1个数的函数count
因此，可以将n用bitset类转化为二进制，然后用count函数统计出其中1的个数
代码：

#include <bitset> 
int NumberOf1(int n){
return bitset<10>(n).count();//这里的10不是10进制，而是初始化的总位数
}

最后

以上就是会撒娇雨为你收集整理的关于统计整数转换为二进制后含多少1的问题的全部内容，希望文章能够帮你解决关于统计整数转换为二进制后含多少1的问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。