LeetCode 191. Number of 1 Bits    原题链接    简单

作者： 作者的头像   yxc ,  2018-06-21 23:03:13 ,  所有人可见 ,  阅读 1738

2


题目描述

给定一个无符号整数，统计其二进制表示中1的个数。

样例1

输入：11
输出：3
解释：整数11的二进制表示是 00000000000000000000000000001011

样例2

输入：128
输出：1
解释：整数128的二进制表示是 00000000000000000000000010000000

算法

(位运算) $O(1)$

每次操作先判断 $n$ 的最低位是否是1，然后将 $n$ 右移一位。
总共操作32次。

时间复杂度分析：总共进行32次操作，每次操作的计算量是 $O(1)$，所以总时间复杂度是 $O(1)$。

C++ 代码

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n)
        {
            res += n & 1;
            n >>= 1;
        }
        return res;
    }
};

1 评论

用户头像
迷弟   2021-02-02 03:22         踩      回复 
int hammingWeight(uint32_t n) { //方法2
        int res = 0;
        while (n){
            res += 1; //每次成功操作一次即1的数量加一。
            n &= n - 1; //每次消掉最右侧的1(不一定是末尾)
        } //玄学好吧，LC先加后异或就是0ms..不然就是4ms 可能小数据比较多?
        return res;
    }