Leetcode 191.位1的个数

发表于 | 更新于 | 分类于

题目描述

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

示例 1:

1
2
3
输入：00000000000000000000000000001011  
输出：3  
解释：输入的二进制串 00000000000000000000000000001011 中，'1'。

示例 2:

1
2
3
输入：00000000000000000000000010000000  
输出：1  
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3:

1
2
3
输入：11111111111111111111111111111101  
输出：31  
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为'1'。

进阶:

如果多次调用这个函数，你将如何优化你的算法？

题目分析

可以循环的对输入数与1取与, 如结果为1则返回结果加1, 后右移1位.

源码

1
2
3
4
5
6
7
8
9
10
11
class Solution { // 手动取每一位
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n != 0) {
            if(n&1 == 1) ++count; // 如数和1取与为1则结果加1
            n >>=1;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
class Solution { // 使用STL的bitset
public:
    int hammingWeight(uint32_t n) {
        bitset<32> b(n);
        // 由于题中已说是32位无符号整数, 则可以使用bitset
        return b.count();
    }
};
0%