leetcode 剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

示例 1：

输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

提示：

输入必须是长度为 32 的 二进制串 。

思路一：& 和 >> （使用 按位与 和 右移运算符 逐位判断）

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    
public:
    int hammingWeight(uint32_t n) {
    
        int sum=0;
        while(n){
    
        	sum+=(n&1);  // (n&1) 是判断最后一位是否为1。按位与的运算规则是：2进制数的对应位置中只有2个数字都为1，结果才为1
        				 //因为1的二进制表示形式的32位中只有最后一个是1，所以前31位按位与之后都为0，那么就是判断最后一位是否都为1，若都是1则为真， (n&1) 的值为1，否则为0
        	n>>=1; //右移1位将最后一位删掉，高位正数补0，负数补1
        }
        return sum;
    }
};

思路二：使用 n&(n-1)

class Solution {
    
public:
    int hammingWeight(uint32_t n) {
    
        int sum=0;
        while(n){
    
            n&=(n-1);  //每一次的 n&=(n-1) 都将32位中最右侧的1变为0，直到最后n为0
            ++sum;
        }
        return sum;
    }
};

关于位运算（按位与、按位或、异或）可看 位运算（按位与、按位或、异或）