剑指offer编程题—二进制中1的个数

题目描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

解题思路

思路一：暴力方法

方法1：除2取模法

#include <iostream>
using namespace std;

int main() {
    int val;
    int res;
    cin>>val;
    while(val){
        if(val%2) ++res;
        val /= 2;
    }
    cout<<res<<endl;
    return 0;
}

该方法只能作为参考，不能通过所有用例测试，对于负数，计算机是使用补码存储数据的，例如-1，在计算机中的存储形式为（11111111），该方法计算-1中1的个数却是1，显然是不对的。

方法2：二进制移位法

#include <iostream>
using namespace std;

int main() {
    int val;
    int res=0;
    cin>>val;
    while(val){
        if(val&1) ++res;
        val >>=1;
    }
    cout<<res<<endl;
    return 0;
}

该方法将被求整数的最后一位二进制与0x000...0001进行&操作，并不断右移，知道整数为0，但是这里还是有问题的：正数右移最高位是补0，但是负数右移后最高位是补1的，这就意味对于负数上述方法会陷入死循环。
对于上述方法转换一下思路，可以在不改变被求整数的基础上，将0x0000...0001中的1不断左移，然后与整数进行与操作。

#include <iostream>
using namespace std;

int main() {
    int val;
    int res=0;
    cin>>val;
    int m=1;
    while(m){
        if(val&m) ++res;
        m <<=1 ;
    }
    cout<<res<<endl;
    return 0;
}

这个算法是可行的，但是需要运行32次。
时间复杂度：O(32)
空间复杂度：O(1)

思路二：技巧方法

对于上面的可行算法，在当前位是0的情况下，还是会进行判断，然后一位一位的移动。
其实这里是可以从右到左的第一位1直接判断的，遇到0可以直接跳过。
例如：val（1101 0000），val-1（1100 1111），val&(val-1) = 1100 0000.
所以只要不断将val&(val-1)赋值给val，就可以用少数的循环计算出1的数量。

#include <iostream>
using namespace std;

int main() {
    int val;
    int res=0;
    cin>>val;
    while(val){
        ++res;
        val =val&(val-1);
    }
    cout<<res<<endl;
    return 0;
}

时间复杂度：O(n)，n为1的数量；
空间复杂度：O(1).

思路三：使用C++库函数

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    int val;
    int res=0;
    cin>>val;
    bitset<32> b(val);
    res = b.count();
    cout<<res<<endl;
    return 0;
}

最后编辑于：2020.10.11 11:06:53