求自然数中K与bit_count(M)对应N值的通用计算公式

我需要一个简洁的通用公式，解决两个关联问题：

• 给定特定的bit_count（二进制表示中1的个数）M，求该bit_count第N次出现时对应的自然数K；
• 已知自然数K及其bit_count值M，求N——N是0到K-1范围内bit_count等于M的自然数的数量。

举个具体例子：已知K=123456789123456789123456789，它的bit_count值M=50，求对应的N值。

验证用示例代码 #

以下是长度为5时的遍历验证代码：

length = 5
for K in range(2**length):
    bits = bin(K)[2:].zfill(length)
    M    = K.bit_count() # 二进制序列中1的个数
    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
...（省略部分结果）

已找到的部分场景公式 #

当N<=M时，存在以下对应公式：

• 由K求N：N = (K - sum(2**i for i in range(M))).bit_count()
• 由N求K：K = sum(2**i for i in range(M)) + sum(2**(M-1-i) for i in range(N))

这类场景约占总情况的一半，现寻求适用于所有场景的通用计算公式。

内容的提问来源于stack exchange，提问作者Bobby Ocean