最后更新于1年前
这有帮助吗?
题目链接:
通过遍历二进制位,统计其中 1 的个数
1
在循环中,将计数器 count 加 1,然后将 num 与 num-1 进行按位与运算,将结果存储到 num 中
count
num
num-1
按位与运算的结果是将 num 的最后一位 1 变成 0,因此每次循环都会将一个 1 变成 0
0
当 num 变成 0 时,循环结束
func hammingWeight(num uint32) int { count := 0 // 循环遍历二进制位,直到 num 变成 0 for num != 0 { count++ // 将计数器 count 加 1 num &= num - 1 // 将 num 与 num-1 进行按位与运算,将结果存储到 num 中 // 按位与运算的结果是将 num 的最后一位 1 变成 0,因此每次循环都会将一个 1 变成 0 } return count }
时间复杂度: 时间复杂度是 O(k)O(k)O(k),其中 kkk 是二进制表示中 111 的个数。在函数中,需要遍历二进制位,对于每个 111,需要执行一次按位与运算
空间复杂度: 空间复杂度是 O(1)O(1)O(1),函数只使用了常数个变量来存储中间结果,没有使用额外的空间