This question already has answers here:

Finding the total number of set-bits from 1 to n
(15个答案)
我看到一个代码,用于计算范围(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)

有谁能解释一下吗?谢谢。

最佳答案

假设你有一个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)+1count(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的定义。

关于algorithm - 如何理解代码:计算范围(0:a)中的1的数量,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10536903/

10-11 22:05