比特位计数

1. 题目描述

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

2. 思路

1. 思路一
   • 与1操作
2. 思路二
   1. 奇数偶数

3. 实现

3.1. 与1

package main

func countBits(num int) []int {
	res := make([]int, 0)
	for i := 0; i <= num; i++ {
		res = append(res, countBit1(i))
	}

	return res
}

func countBit1(num int) int {
	bit := 1
	count := 0
	for i := 0; i < 32; i++ {
		if num&bit != 0 {
			count++
		}
		bit <<= 1
	}
	return count
}

3.2. 奇数偶数

func countBits(n int) []int {
    res := make([]int, n+1)
    for i := 1; i <= n; i++ {
        if i % 2 == 1 {
            res[i] = res[i-1]+1
        }else {
            res[i] = res[i/2]
        }
    }
    return res
}

4. 参考

• 清晰的思路 - 比特位计数 - 力扣（LeetCode）
• 比特位计数 - 比特位计数 - 力扣（LeetCode）