题目描述

用vector模拟计算机中存放的二进制数，对1进行计数。

C++ 代码

int NumberOf1(int n) {
        int cnt=0;
        if(n==0)
        return 0;
        if(n==INT_MIN)//int 最小值-2147483848,刚好是-2^31,取绝对值后会超过int上限（2147483647）,当成特殊情况处理
        return 1;
        vector<int> a,b;
        if(n<0)//先求原码，再求反码，最后求补码。都是31位，符号位固定是1，不参与计算
        {
            n=abs(n);
            while (n)
            {
                b.push_back(n%2);//反原码（不足31位）
                n=n/2;
            }
            for(int i=0;i<31-b.size();i++)
            a.push_back(0);//补足原码前的0
            for(int i=b.size()-1;i>=0;i--)
            a.push_back(b[i]);//正原码（31位）
            b.clear();
            for(int i=0;i<a.size();i++)
            b.push_back(1^a[i]);//正反码（31位）
            a.clear();
            for(int i=b.size()-1;i>=0;i--)//计算补码
            {
                if(b[i]==1)//b[i]为1，加1会进位，所以一直压入0，直到遍历到b[i]为0，停止进位，这一位写1
                a.push_back(0);
                else
                {
                    a.push_back(1);
                    for(int j=i-1;j>=0;j--)
                    a.push_back(b[j]);//反补码
                    break;
                }
            }//由于补码已经确定，正着反着都无所谓，所以直接计数。不用翻转
            for(int x:a)
            {
                if(x==1)
                cnt++;
            }
            cnt++;//负数符号位加一
            return cnt;
        }
        else//n大于0,直接计算原码，对原码的1计数
        {
            while (n)
            {
                b.push_back(n%2);//反原码
                n=n/2;
            }
            for(int x:b)
            {
                if(x==1)
                cnt++;
            }
            return cnt;
        }

    }

示例1

输入-2
第一次b中存放：
0 1 //2应该是1 0，是反着的
第一次a中存放：
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 //共31位，没有符号位，是正常顺序的-2的原码
第二次b中存放：
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 //共31位，没有符号位，是正常顺序的-2的反码
第二次a存放：
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 //共31位，是反着顺序的-2的补码，不含符号位
之后对1计数，共30个，加上符号位的1，共31个
负数计算都差不多这样，只有-2147483848，取绝对值超过int上限，当成特殊情况处理

至于正数就很简单了，直接计算原码即可