algorithm - 如何理解代码：计算 range(0:a) 中 1 的个数

Question

我看到一个代码用于计算范围（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) ;
}

我可以理解计数功能，但真的无法理解求解中的递归：

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

有没有人可以解释一下？非常感谢。

Answer 1

假设你有号码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作为总和的定义。