统计所有设置的位总和，直到第N个

Question

任何人都可以帮我破解任何公式或代码，而不是 O(n) 来计算最多 N 个设置位数的总和

N    Bit

Ex: 1 -> 1 
    2 -> 1 + 1 (this 1 is previous one as we are summing those)
    3 -> 4
    4 -> 5
    5 -> 7
    |    
    |
    Nth term formula???

我尝试破解这样的模式：

for first bit  2^0: 1 and 0 makes pattern of 01010101---------Nth
for second bit 2^1: 1 and 0 makes pattern of 00110011---------Nth
for third bit  2^2: 1 and 0 makes pattern of 00001111---------Nth

Answer 1

让我们寻找依赖关系。

0001111**

（

k

个）模式的结果是

k*2^(k-1)

，因此包含唯一一个“1”(

2^k

) 的模式的结果是

1 + k*2^(k-1)

。因此，我们可以分离最高有效一位 (MSB)，获取相应的 2 次幂的数字计数，然后将右尾值计数和右尾值本身相加（因为 MSB）。 Python代码：

def cnt_ones(n):
    if n==0: return 0
    leftbit = 1
    bitnum = 0
    cnt = 0

    while leftbit*2 <= n:  #find power of two for MSB
        leftbit <<= 1
        bitnum += 1

    while leftbit:  #now check bits from left to right
        if n & leftbit:
            cnt += 1    +        (leftbit//2) * bitnum + + (n & (leftbit - 1))
                # MSB bit itself   
                               #count for numbers before this power of two
                                                           # tail value without lrger bits       
        leftbit >>= 1
        bitnum -= 1
    return cnt

0 0
1 1
2 2
3 4
4 5
5 7
6 9                 
7 12     #3*2^2
8 13     #1+3*2^2
9 15
10 17
11 20
12 22
13 25
14 28   # 1 + 3*2^2 + (14-8) + count(14-8) 
15 32
16 33
17 35
18 37
...
30 75
31 80
32 81
33 83