区间的汉明权重

Question

我的任务是计算区间 [1,10^16] 的 1 位位数。在这种情况下，Loop 显然是无法使用的，我听说有一种算法可以解决这个问题。谁能帮忙？

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

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

Answer 1

区间 [1，n] 中的 1 位数是区间 [1,2^m] 中的 1 位数

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

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 位。
让我们 x = 2^k + b， f(1， x( = f(0， x( = f(0， 2^k + b( = f(0， 2^k - 1( + f(2^k

4. ， 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 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 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， b(

   显然，我们必须递归计算 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