跳至主要內容

0191. 位1的个数

ITCharge大约 1 分钟

0191. 位1的个数open in new window

  • 标签:位运算、分治
  • 难度:简单

题目链接

题目大意

描述:给定一个无符号整数 nn

要求:统计其对应二进制表达式中 11 的个数。

说明

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

示例

  • 示例 1:
输入:n = 00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'
  • 示例 2:
输入:n = 00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'

解题思路

思路 1:循环按位计算

  1. 对整数 nn 的每一位进行按位与运算,并统计结果。

思路 1:代码

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            ans += (n & 1)
            n = n >> 1
        return ans

思路 1:复杂度分析

  • 时间复杂度O(k)O(k),其中 kk 是二进位的位数,k=32k = 32
  • 空间复杂度O(1)O(1)

思路 2:改进位运算

利用 n & (n - 1)。这个运算刚好可以将 nn 的二进制中最低位的 11 变为 00

比如 n=6n = 6 时,6=110(2)6 = 110_{(2)}61=101(2)6 - 1 = 101_{(2)}110 & 101 = 100

利用这个位运算,不断的将 nn 中最低位的 11 变为 00,直到 nn 变为 00 即可,其变换次数就是我们要求的结果。

思路 2:代码

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            n = n & (n - 1)
            ans += 1
        return ans

思路 2:复杂度分析

  • 时间复杂度O(logn)O(\log n)
  • 空间复杂度O(1)O(1)