比特位计数

2022-02-21

题目链接

一、O(nlog(n))解法

核心是理解 x &(x-1) 的作用是把x的最低位的1置零。

def countOnes(x: int) -> int:
            ones = 0
            while x > 0:
                x &= (x - 1)
                ones += 1
            return ones

计算一个数的1比特位的个数。然后依次计算即可。

二、O(n)解法

核心思路有两点。

若i大于j 且i的二进制表示只多了一个1，则

令bits[i] 表示i的1比特的个数。

bits[i] = bits[j] + 1

第二点是最高有效位的概念。对于正整数x，如果可以知道的最大的正整数y，使得 y <= x且y是2的整数次幂。则y的二进制表示中只有最高位为1，其余都是0，则称y为x的最高有效位。

又知道，仅当y&(y-1)等于0时，y是2 的整数次幂。

则易知：

bits[x] = bits[x-y] + 1

bits = [0]
highBit = 0

for i in range(1, n+1):
    if i&(i-1) == 0:
        highBit = i
    bits.append(bits[i-highBit]+1)

return bits