2

range(0,a) 内のすべての整数の 1 ビットの総数を計算するために使用されるコードが表示されます。

int count(int a)
{
    int sum = 0;
    while(a)
    {
        sum +=1;
        a = a & (a-1);
    }
    return sum;
}
long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + count(a) ;
 return ((long)a + 1) / 2 + 2 * solve(a / 2) ;
}

count 関数は理解できますが、solve の再帰は本当に理解できません:

if (a%2 ==1)
   solve(a) = (a+1)/2 + 2* solve(a/2)

少し説明できる人はいますか？どうもありがとう。

4

1 に答える 1

2

あなたが番号を持っていて、n = 2X+1見つけたいとしましょう

solve(n) = sum of count(i) for 0<=i<=n

これは次のようになります。

solve(n) = sum of count(2j)+count(2j+1) for 0<=j<=X

count(2j+1) = count(2j)+1となのでcount(2j) = count(j)、次のように簡略化できます。

solve(n) = sum of 2*count(2j)+1 for 0<=j<=X
         = sum of 2*count(j)+1 for 0<=j<=X
         = 2*(sum of count(j) for 0<=j<=X) + (sum of 1 for 0<=j<=X)
         = 2*solve(X) + X + 1
         = 2*solve(floor(n/2)) + (n+1)/2

これはあなたの漸化式です。

が偶数の場合n（したがって、形式ではない場合2X+1）、次の式を使用できます

solve(n) = count(n) + solve(n-1)

solveこれは、上記の合計としての定義から直接得られます。

于 2012-05-10T15:15:32.007 に答える