Counting Bits

Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array. For num = 5 you should return [0,1,1,2,1,2].
给定一个非负整数 num,返回一个数组,数组中的值为 0 到 num 间相对应整数其二进制表示中 1 的个数。举例来说,若 num 为 5,则返回的数组为 [0,1,1,2,1,2]。

首先,求二进制表示中 1 的个数是比较简单的。只要把这个数不断地除 2,再把得到的余数相加即可。
拿 5 来说,
$ 5 ÷ 2 = 2 … 1 $
$ 2 ÷ 2 = 1 … 0 $
$ 1 ÷ 2 = 0 … 1 $
因此二进制 101 中的 1 的个数为 2。

但若是求 0 到 num 之间所有数的 1 的个数,每个数都这么算就太慢了。我们找找看有什么规律可以让我们省掉一些计算。

1
2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1

1 的个数看上去好像有点重复性,但没找到具体的规律。在 2 的指数次时,如 4、8 时,个数都变为了 1。仔细想想也很简单,4、8 二进制表示分别为 100、1000,之前的数进 1 而使 1 的个数锐减。

1
000 001 010 011 100 101 110 111

那再从二进制的角度看看。上面是 0 到 7 的二进制表示。仔细看的话,后 4 个数字若除去第 1 位,与前 4 个数字的规律是一样的。也就是进位之后,除第 1 位,其他位数的变化和以前是重复的。
[2,3] 与 [0,1] 的个位数变化是相同的,[4,7] 和 [0,3] 的个十位变化相同,[8,15] 和 [0,7] 的个十百位变化相同。这样我们就可以省略掉大量重复的运算,用 $O(n)$ 的时间计算出结果。

具体算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
if num == 0:
return [0]
else:
result = [0]
initial = 1
while True:
result = result + list(map(lambda x: x + 1, result))
initial *= 2
if num < initial:
break
return result[0:num+1]