题解 | #求int型正整数在内存中存储时1的个数#

描述
        输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。

输入描述：
输入一个整数（int类型）
输出描述：
这个数转换成2进制后，输出1的个数

示例1
输入： 5
输出： 2

方法一：除留取余统计法
核心思想：
        整数对2取余，统计余数为1的个数，然后对整数除2。循环直到整数为0，输出统计的1个数。

图解：

核心代码：

#include<iostream>
using namespace std;

void count_one(int n){
    int count = 0;
    while(n){
        if(n%2)     //取余统计1的个数
            count++;
        n/=2;
    }
    cout<<count<<endl;
}

int main(){
    int n;
    cin>>n;
    count_one(n);
    return 0;
}

时间复杂度O(logN)
空间复杂度O(1)
时间复杂度说明：因为每次循环都是除以2，假设循环T次，则2的T次方为N，因此循环次数T为logN，时间复杂度为O(logN)；因为程序只引入了一个临时变量，空间复杂度为O(1)

方法二：移位法
核心思想：
        设置标志位flag，初始值为1，将flag与整数进行与操作，并统计结果为1的次数，同时循环左移flag直到flag为0跳出循环

核心代码：

#include<iostream>
using namespace std;

void count_one(int n){
    int count = 0;
    unsigned int flag=1;
    while(flag){
        if(n&flag)     //逐位检测当前位是不是1，是的话则统计
            count++;
        flag=flag<<1;  //左移flag
    }
    cout<<count<<endl;
}

int main(){
    int n;
    cin>>n;
    count_one(n);
    return 0;
}

时间复杂度O(logN)
空间复杂度O(1) 时间复杂度说明：因为每次循环都是左移2，相当于除以2，假设循环T次，则2的T次方为N，因此循环次数T为logN，时间复杂度为O(logN)；因为程序只引入了一个临时变量，空间复杂度为O(1)