求1到N数字二进制置位总和的亚线性时间公式或代码

核心思路 #

你观察到的规律完全正确：二进制的每一位（从最低位开始记为第k位，对应权重2^k）都有固定重复模式：

• 第k位的重复周期是2^(k+1)，每个周期内前2^k个数该位为0，后2^k个数该位为1。
• 我们只需要计算每一位在1~N范围内出现1的次数，再把所有位的次数相加，就能得到总和。

计算公式推导 #

对于第k位（k从0开始计数）：

1. 计算完整周期数：full_cycles = (N + 1) // (2 << k)（2 << k等价于2^(k+1)）
2. 每个完整周期贡献2^k个1，完整周期总次数：full_cycles * (1 << k)
3. 剩余未完成周期的数字个数：remainder = (N + 1) % (2 << k)
4. 剩余部分中该位为1的数量：max(0, remainder - (1 << k))
5. 第k位总置位次数 = 完整周期贡献 + 剩余部分贡献

将所有k（从0到N的二进制最高位）的结果相加，就是1到N的二进制置位总和。

代码实现（Python） #

def count_set_bits_sum(n):
    total = 0
    k = 0
    while (1 << k) <= n:
        cycle = 2 << k
        full_cycles = (n + 1) // cycle
        total += full_cycles * (1 << k)
        remainder = (n + 1) % cycle
        total += max(0, remainder - (1 << k))
        k += 1
    return total

示例验证 #

以N=5为例：

• k=0（最低位）：周期2，完整周期数3，贡献3*1=3；剩余0，无额外贡献，累计3
• k=1：周期4，完整周期数1，贡献1*2=2；剩余2，max(0,2-2)=0，累计3+2=5
• k=2：周期8，完整周期数0，剩余6，max(0,6-4)=2，累计5+2=7
  结果与示例完全一致。

内容的提问来源于stack exchange，提问作者Shivam Kumar