number-of-1-bits.md

位1的个数

题目链接: https://leetcode.cn/problems/number-of-1-bits

解题思路：

1. 通过遍历二进制位，统计其中 1 的个数
2. 在循环中，将计数器 count 加 1，然后将 num 与 num-1 进行按位与运算，将结果存储到 num 中
3. 按位与运算的结果是将 num 的最后一位 1 变成 0，因此每次循环都会将一个 1 变成 0
4. 当 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)$$，其中 $$k$$ 是二进制表示中 $$1$$ 的个数。在函数中，需要遍历二进制位，对于每个 $$1$$，需要执行一次按位与运算
• 空间复杂度： 空间复杂度是 $$O(1)$$，函数只使用了常数个变量来存储中间结果，没有使用额外的空间