首页 计算机 语言 C++

# 191 位 1 的个数 (easy) 2023-2-25

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

首先是我自己写的解法，占用空间大，而且借助循环，速度也较慢。写的时候需要注意运算的优先级。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        for (int i=0;i<32;i++) {
            ret += (n-((n>>1)<<1));
            n = n>>1;
        }
        return ret;
    }
};

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户

内存消耗：5.8 MB, 在所有 C++ 提交中击败了 86.21% 的用户

投机取巧的写法：

class Solution {
public:
    int hammingWeight(uint32_t n) {
        return bitset<32>(n).count();
    }
};

借助了 C++ 中专门进行位运算的库 bitset, 可以采用头文件 <bitset> 引入。

将 java 中 bitCount 源码转换过来的写法如下。

class Solution {
public:
	int hammingWeight(uint32_t n) {
		n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
		n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
		n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
		n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
		n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
		return n;
	}
};