为了更好的明天,坚持刷 LeetCode

题目

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

提示:

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

解法一 - 位运算

解题思路

我们知道 $n & (n−1)$ 会将 $n$ 的最低位的 1 变为 0,那么我们可以利用这个性质计算 $n$ 的二进制位中 1 的个数,即直到 $n == 0$ 时 $n & (n−1)$ 运算的次数。

代码

func hammingWeight(num uint32) (n int) {
    for ; num > 0; num &= num - 1 {
        n++
    }
    return
}

执行结果

执行用时:0 ms,在所有 Go 提交中击败了 100.00% 的用户
内存消耗:1.9 MB,在所有 Go 提交中击败了 61.94% 的用户

复杂度分析

  • 时间复杂度:$O(logn)$。循环次数等于 $n$ 的二进制位中 1 的个数,最坏情况下 $n$ 的二进制位全部为 1。
  • 空间复杂度:$O(1)$

题目链接

191. 位1的个数

相似题目