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

我不懂 Python，所以这是 Ruby。该算法应该易于翻译。这个想法是，对于每个设置位（从小到大），计算该位左侧相同的所有数字，该位及其右侧具有相同数量的设置位，但没有该位已设置。

• 从最小到最大遍历输入的位。
• 跟踪看到的设置位和看到的总位。
• 每次遇到设置位时，对具有相同数量的设置位但最大设置位（比当前索引）更小的所有数字进行计数。
• 例如，当达到 10100 中较小的 1 时，我们将计数加 2，因为有 2 个数字具有 1 个设置位和一个较小的最大设置位：10 和 01。

代码：

def g(k)
  set_bits_seen = 0
  all_bits_seen = 0
  
  total = 0
  
  while k > 0
    all_bits_seen += 1
    
    if k % 2 == 1 # cur bit is set
      set_bits_seen += 1
      if all_bits_seen > set_bits_seen
        total += n_choose_k(all_bits_seen - 1, set_bits_seen)
      end
    end
    k /= 2
  end
  return total
end

def n_choose_k(n, k)
  return 1 if k == 0 or k == n
  (k + 1 .. n).reduce(:*) / (1 .. n - k).reduce(:*)
end

结果：

1.upto(20) do |i|
  puts "#{i.to_s(2)}  --  #{g(i)}"
end

1  --  0
10  --  1
11  --  0
100  --  2
101  --  1
110  --  2
111  --  0
1000  --  3
1001  --  3
1010  --  4
1011  --  1
1100  --  5
1101  --  2
1110  --  3
1111  --  0
10000  --  4
10001  --  6
10010  --  7
10011  --  4
10100  --  8

对于你的大例子：

> g(123456789123456789123456789)
=> 3594960708495168399327022

简单的解决方案：

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 的数字生成 0 位置的唯一组合，然后计算这些数字：

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并且它基本上定义了相同的东西。（看看图表，它并没有变得更好：https://oeis.org/A079071/graph）

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

将数字表示为位的组合并计算组合索引：

from more_itertools import combination_index
from math import comb

K = 123456789123456789123456789

M = K.bit_length()
c = [i for i, b in enumerate(f'{K:b}') if b == '1']
N = comb(M, len(c)) - 1 - combination_index(c, range(M))

print(N)

输出（与戴夫的相同）：

3594960708495168399327022

啊该死，我刚刚意识到你正在追求“一个简单的公式”。那好吧。也许这对于来这里寻找简单代码的人来说仍然有用。