Python 大小为M的第N位_计数(或人口计数)的公式

我有兴趣找到一个简单的公式来确定特定bit_num在自然数序列中出现的第n次.具体来说，下表中K和N之间的关系是什么.那么，例如，K=123456789123456789123456789中的N是什么，我可以告诉你M是50，但N是什么？

length = 5
for K in range(2**length):
    bits = bin(K)[2:].zfill(length)
    M    = K.bit_count() # numbers of "1"s in the binary sequence
    N    = sum(1 for i in range(K) if M==i.bit_count())
    print(f'{K: <2}',bits,M,N)

'''
K  bits  M N
0  00000 0 0
1  00001 1 0
2  00010 1 1
3  00011 2 0
4  00100 1 2
5  00101 2 1
6  00110 2 2
7  00111 3 0
8  01000 1 3
9  01001 2 3
10 01010 2 4
11 01011 3 1
12 01100 2 5
13 01101 3 2
14 01110 3 3
15 01111 4 0
16 10000 1 4
17 10001 2 6
18 10010 2 7
19 10011 3 4
20 10100 2 8
21 10101 3 5
22 10110 3 6
23 10111 4 1
24 11000 2 9
25 11001 3 7
26 11010 3 8
27 11011 4 2
28 11100 3 9
29 11101 4 3
30 11110 4 4
31 11111 5 0
...
'''

所以，我似乎已经解决了一半.看来

N = (K-sum(2**i for i in range(M)).bit_count()

每当N<=M.这似乎是因为，

K = sum(2**i for i in range(M)) + sum(2**(M-1-i) for i in range(N))

再次，每当N<=M.似乎大约有一半的时间出现N<=M.

length = 5
for K in range(2**length):
    bits = bin(K)[2:].zfill(length)
    M    = K.bit_count() # numbers of "1"s in the binary sequence
    N    = sum(1 for i in range(K) if M==i.bit_count())
    if N <= M:
        A = sum(2**i for i in range(M)) + sum(2**(M-1-i) for i in range(N))
        B = (K - sum(2**i for i in range(M))).bit_count()
    else:
        A = '-'
        B = '-'
    print(f'{K: <2}',bits,M,N,A,B)