本文介绍一种基于组合数学的 o(log k) 时间复杂度算法，用于精确求解：给定正整数 k，其二进制表示中含 m 个 1（即 bit_count = m），在所有 ≤ k 的非负整数中，它是第几个满足 bit_count = m 的数（即索引 n，从 0 开始计数）。
本文介绍一种基于组合数学的 o(log k) 时间复杂度算法，用于精确求解：给定正整数 k，其二进制表示中含 m 个 1（即 bit_count = m），在所有 ≤ k 的非负整数中，它是第几个满足 bit_count = m 的数（即索引 n，从 0 开始计数）。
该问题本质是：对固定比特数 M，将所有 bit_count = M 的非负整数按升序排列（即 0, 1, 2, …），求 K 在该子序列中的零基索引 N。例如，bit_count = 2 的序列前若干项为：3 (11₂), 5 (101₂), 6 (110₂), 9 (1001₂), 10 (1010₂), 12 (1100₂), …，则 K=5 对应 N=1。
直接遍历 0 到 K 显然不可行（尤其当 K 超过 10²⁰ 时）。高效解法的核心思想是逐位枚举 + 组合计数：从最低位（LSB）向最高位扫描 K 的二进制表示，每当遇到一个置位（bit = 1），就统计所有“更小但具有相同 M 值”的数——即：保持更高位不变，将当前位设为 0，并在右侧剩余位中，选择恰好 M - 已统计置位数 个位置填 1 的方案数。
具体步骤如下：
- 初始化 set_bits_seen = 0（已遍历的 1 的个数）、all_bits_seen = 0（已遍历的总位数）、total = 0（累计 N 值）；
- 从 LSB 开始逐位处理 K（等价于循环 while k > 0，每次 k //= 2）；
- 每轮 all_bits_seen 加 1；
- 若当前位为 1（即 k % 2 == 1）：
- set_bits_seen += 1；
- 此时，若 all_bits_seen > set_bits_seen（即右侧尚有空位可安置剩余 1），则可构造合法数：将当前位强制置 0，右侧 all_bits_seen - 1 位中任选 set_bits_seen 个位置置 1（因更高位已固定为 0，且当前位变 0 后整体更小），方案数为组合数 C(all_bits_seen - 1, set_bits_seen)；
- 将该组合数累加到 total。
关键组合函数 n_choose_k(n, k) 需高效实现（避免阶乘溢出），推荐使用迭代式计算：
def nCk(n, k):
if k n:
return 0
if k == 0 or k == n:
return 1
k = min(k, n - k) # 利用对称性减少计算
num = 1
den = 1
for i in range(k):
num *= n - i
den *= i + 1
return num // den
主算法 Python 实现如下：
def bit_count_rank(k: int) -> int:
if k == 0:
return 0
set_bits = 0
total_bits = 0
rank = 0
temp = k
while temp:
total_bits += 1
if temp & 1: # 当前位为1
set_bits += 1
# 右侧 total_bits-1 位中选 set_bits 个放1（当前位置0，确保更小）
if total_bits > set_bits:
rank += nCk(total_bits - 1, set_bits)
temp >>= 1
return rank
✅ 注意事项：
- 本算法返回的是 严格小于 K 且 bit_count 等于 K 的数的个数，即 K 在其 bit_count 类别中的零基索引（与题中 N 定义完全一致）；
- 时间复杂度为 O(log₂K)，空间复杂度 O(1)，适用于任意大整数（如题中 K = 123456789123456789123456789，输出 N = 3594960708495168399327022）；
- 组合数计算务必使用整数迭代而非浮点或阶乘，防止大数精度丢失或溢出；
- 该方法不依赖预计算或查表，纯数学推导，具备强可移植性（易转译至 C/Java/Rust 等语言）。
综上，该算法将“第 N 个 bit_count = M 的数”这一看似离散的问题，转化为对二进制位权重的组合枚举，是数位 DP 思想的精简典范。掌握此方法，即可在常数内存下瞬时求解千亿级输入的位统计索引。
