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

HJ15 求int型正整数在内存中存储时1的个数

一.题目描述

给出一个正整数，求该正整数在二进制下的1的个数

二.算法(模拟)

可以手动模拟将数准换为二进制表示，记录其二进制下1的个数，下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt=0;
    while(n){
        if(n%2==1){//判断当前位是不是1
            cnt++;//当前位是1计数器加一
        }
        n/=2;//下一位
    }
    cout<<cnt<<endl;
    return 0;
}

时间复杂度：由于数字最多是32位，最多是32次遍历，时间复杂度是常数级别的，所以最后的复杂度是$O(1)O(1)$

空间复杂度：$O(1)O(1)$不需要什么额外空间

三.算法(位运算)

我们可以利用位运算来解决该题，我们可以对所给数的每一个二进制位进行判断，若二进制位是1就计数器加一，输出计数器个数，下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt;
    for(cnt=0;n;n>>=1){
        if(n&1){//和1异或 相同表示是1 不相同表示为0
            cnt++;//是1计数器加一
        }
    }
    cout<<cnt<<endl;
    return 0;
}

时间复杂度：$O(1)O(1)$ 使用位运算并且由于数字最多是32位，最多是32次遍历，时间复杂度是常数级别的，所以最后的复杂度是$O(1)O(1)$

空间复杂度：$O(1)O(1)$ 不需要什么额外的空间

三.算法(数学技巧)

求二进制中1的个数的算法我们可以利用一个n&(n-1)来求出。

1.二进制数n-1后，如果最后一位是0，将向前进一位借2，最后一位为1。如果前一位为0，将继续向前一位借2，加上本身少掉的1，则变为1。直到遇到1，减为0。也就是说每次减一操作就是抹去一位1。

2.重复操作，有多少个1，这个操作就执行多少次。

下面是完整代码：

#include<bits/stdc++.h>   
using namespace std;  
int main(){  
    int n,cn=0;  
    cin>>n;  
    while(n>0){  
        cn++;  
        n&=(n-1);  
    }  
    cout<<cn<<endl;  
    return 0;  
}

时间复杂度：$O(1)O(1)$ 只会循环1的个数次，最多就是32位1,将数n的每一位都遍历一遍，所以复杂度是常数级别的为$O(1)O(1)$

空间复杂度：$O(1)O(1)$ 不需要什么额外的空间