题目描述

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

样例

样例1
输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。

样例2
输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
      一共有31个1。

算法1 右移运算符和且运算

C++ 代码

class Solution {
public:
    int NumberOf1(int n) {
        int num=0;
        unsigned int un=n; //如果是负数,那么在进行移位运算的时候,高位会补1导致出错,所以要转化成无符号整型
        while(un>0)
        {
            if(un&1)
                num++;
            un>>=1;
        }
        return num;
    }

};

算法2

C++ 代码

class Solution {
public:
    int NumberOf1(int n) {
        int num=0;
        unsigned int un=n; //跟算法一同理
        while(un>0)
        {
            un-=un&(-un);   //每次删除n中的一个1,删除了至0,删除了多少次就有多少个1 等价于un-=lowbit(un)
            num++;
        }
        return num;
    }

};