寻求序列1到n的总汉明权重通用公式：log2(n)非整数时现有公式失效

当n是2的幂（即log₂(n)为整数）时，总汉明权重可以用简化公式快速计算：
n * log2(n) / 2

但对于非2的幂的n，需要按二进制每一位的贡献推导通用解法：

通用计算逻辑 #

总汉明权重等于二进制每一位上1出现的次数之和。对于二进制第i位（从0开始计数，最低位为第0位）：

• 该位的循环周期为2^(i+1)，每个周期内有2^i个数的该位为1
• 计算1到n中包含的完整周期数：q = n // (2^(i+1))
• 计算周期外剩余的数：r = n % (2^(i+1))
• 该位的1出现次数为：q * 2^i + max(0, r - 2^i + 1)

将所有位的结果相加，即可得到1到n的总汉明权重。

公式形式 #

总汉明权重 = Σ（i从0到floor(log₂(n))）[ (n // 2^(i+1)) * 2^i + max(0, n % 2^(i+1) - 2^i + 1) ]

示例验证 #

以n=5为例：

• 第0位（2^0=1）：q=5//2=2，r=1 → 2*1 + max(0,1-1+1)=3
• 第1位（2^1=2）：q=5//4=1，r=1 →1*2 + max(0,1-2+1)=2
• 第2位（2^2=4）：q=5//8=0，r=5 →0*4 + max(0,5-4+1)=2
• 总和：3+2+2=7，与实际计算1-5的汉明权重总和一致。

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