This question already has answers here:
Finding the total number of set-bits from 1 to n
(15个答案)
我看到一个代码,用于计算范围(0,a)内所有整数中1位的总数。
我能理解count函数,但真的不能理解solve中的递归:
有谁能解释一下吗?谢谢。
这等于:
由于
这就是你的复发关系。
如果
这直接来自于上面对
(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)+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
的定义。关于algorithm - 如何理解代码:计算范围(0:a)中的1的数量,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10536903/
10-11 22:05