0191. 位1的个数 #
- 标签:位运算
- 难度:简单
题目大意 #
描述:给定一个无符号整数 $n$。
要求:统计其对应二进制表达式中 $1$ 的个数。
说明:
- 输入必须是长度为 $32$ 的二进制串。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:循环按位计算 #
- 对整数 $n$ 的每一位进行按位与运算,并统计结果。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(k)$,其中 $k$ 是二进位的位数,$k = 32$。
- 空间复杂度:$O(1)$。
思路 2:改进位运算 #
利用 n & (n - 1)
。这个运算刚好可以将 $n$ 的二进制中最低位的 $1$ 变为 $0$。
比如 $n = 6$ 时,$6 = 110_{(2)}$,$6 - 1 = 101_{(2)}$,110 & 101 = 100
。
利用这个位运算,不断的将 $n$ 中最低位的 $1$ 变为 $0$,直到 $n$ 变为 $0$ 即可,其变换次数就是我们要求的结果。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(\log n)$。
- 空间复杂度:$O(1)$。