大小为 M 的第 N 个 bit_count（或人口计数）的公式

Question

我有兴趣找到一个简单的公式来确定自然数序列中特定 bit_count 出现的第 n 次。具体来说，下表中

K

和

N

之间是什么关系。那么，比如说，

N

的

K=123456789123456789123456789

是什么，我可以告诉你

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)

Answer 1

简单的解决方案：

def count_same0(k: int) -> int:
    s = 0
    m = k.bit_count()
    for n in range(k):
        if n.bit_count() == m:
            s += n
    return s

但是，您可以尝试仅生成具有特定位计数的所有数字<

k

，然后对这些数字进行计数。

这是一个简单的尝试：

def count_same1(k: int) -> int:
    from itertools import permutations
    from math import log2, floor

    m = k.bit_count()
    positions = floor(log2(k)) + 1  # the total number of bit positions 

    s = 0
    # start generating unique permutations of positions #bits
    ps = set()
    for p in permutations([0] * (positions-m) + [1] * m):
        if p not in ps:
            ps.add(p)
            n = 0
            for b in p:
                n = (n << 1) | b
            # stop when we first exceed k
            if n >= k:
                break
            s += n

    return s 

这可行，但效率非常低，因为它仍然必须生成所有不唯一的排列。最后，生成排列比仅仅计算位数要慢得多。

相反，最好为具有一定数量 1 的数字生成零位置的唯一组合，然后计算这些数字：

def gen_int_n_ones(n: int) -> Generator[int, None, None]:
    from itertools import combinations

    z = 0
    while True:
        bits_cs = list(combinations(range(1, n), z))
        yield from (sum(0 if i in bits else 2**(n-(i+1)) for i in range(n)) for bits in bits_cs)
        z += 1
        n += 1


def count_same2(k: int) -> int:
    s = 0
    for n in gen_int_n_ones(k.bit_count()):
        if n >= k:
            break
        s += n

    return s

然而，简单的解决方案使用的操作非常高效，只测试所有数字会更有效，而不是找出要避免的数字。

尝试运行这个：

def main():
    from timeit import timeit

    for x in range(1, 100):
        print(x, count_same0(x), count_same1(x), count_same2(x))
        print(
            timeit(lambda: count_same0(x), number=10000), 
            timeit(lambda: count_same1(x), number=10000), 
            timeit(lambda: count_same2(x), number=10000)
        )

您会发现

count_same0

无疑是最快的（事实上，只是快而已），并且

count_same2

比

count_same1

更好，但不接近

count_same0

。

所以我认为简单的答案确实是：

def n_for_k(k: int) -> int:
    b = k.bit_count()
    return sum(1 for i in range(k) if i.bit_count() == b)

但是，对于您的示例值

123456789123456789123456789

，这将需要很长时间才能完成。我怀疑是否有一个已知的更简单的解决方案，因为（在如上所述解决之后）我也在 OEIS 上找到了序列：https://oeis.org/A079071并且它基本上定义了相同的东西。

谁或什么任务让你去解决这个问题？