algorithm - 区间的汉明权重

Question

我的任务是计算区间 [1,10^16] 的 1 位数。对于这种情况，循环显然无法使用，我听说有一种算法可以解决这个问题。任何人都可以帮忙吗？

更一般地，区间 [1,n] 中的 1 位数量的算法会很好。

如果这有帮助，我认为区间 [1,2^n-1]，n 个正整数的 1 位数是 n*2^(n-1)。

Answer 1

区间 [1,n] 中的 1 位数是区间 [1,2^m] 中的 1 位数加上区间 [1,n-2^m] 中的 1 位数加上 n - 2^米。

m 是⌊log(n)/log2⌋。

Answer 2

1. 令 f(A,B) = 从 A 到 B 的 1 位数，包括 A 和 B。
2. 我也认为：f(1,2^k-1) = k*2^(n-1)
3. 显然，f(1, x) = f(0, x) 因为 0 没有 1 位。

4. 让我们 x = 2^k + b, f(1, x) = f(0, x) = f(0, 2^k + b) = f(0, 2^k - 1) + f(2^k , 2^k + b)

   关键问题是 f(2^k, 2^k + b)

   2^k = 1 0 0 0 ... 0 0

   2^k + 1 = 1 0 0 0 ... 0 1

   2^k + 2 = 1 0 0 0 ... 1 0

   2^k + 3 = 1 0 0 0 ... 0 1

   ……

   2^k + b = 1 0 0 0 ... ? ?

   显然，从 2^k 到 2^k + b 的每个数字的第一位都有 1 位。从 2^k 到 2^k + b 有 (b+1) 个整数。

   我们可以删除第一个 1 位。它变成了下面。

   0 = 0 0 0 0 ... 0 0

   1 = 0 0 0 0 ... 0 1

   2 = 0 0 0 0 ... 1 0

   3 = 0 0 0 0 ... 0 1

   ……

   b = 0 0 0 0 ... ? ?

   所以，f(2^k, 2^k + b) = (b+1) + f(0, b)。

   f(0, x) = f(0, 2^k - 1) + f(2^k, 2^k + b) = f(0, 2^k - 1) + (b+1) + f( 0，乙）

   显然，我们必须递归计算 f(0,b)。

5. 举一个第 4 步的例子。

   对于 f(1, 31) = 80，并且 31 有 5 个 1 位。

   所以 f(1, 30) = 80 - 5 = 75;

   让我们使用步骤 4 的方法计算 f(1, 30)。

   f(1, 30) = f(0, 30)

   = f(0, 15) + f(16, 30)

   = 32 + 15 + f(0, 14)

   = 47 + f(0, 14)

   = 47 + f(0, 7) + f(8, 14)

   = 47 + 12 + 7 + f(0, 6)

   = 66 + f(0, 6)

   = 66 + f(0, 3) + f(4, 6)

   = 66 + 4 + 3 + f(0, 2)

   = 73 + f(0, 2)

   = 73 + f(0, 1) + f(2, 2)

   = 74 + f(2, 2)

   = 74 + 1 + f(0， 0)

   = 75