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。

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. 明らかに、0 には 1 ビットがないため、f(1, x) = f(0, x) です。

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、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