I see a code that is used to calculate the total number of 1-bits in all integers in range(0,a).
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) ;
}
I can understand the count function, but really can not understand the recurrence in solve:
if (a%2 ==1)
solve(a) = (a+1)/2 + 2* solve(a/2)
Is there anybody who can explain a bit it ? Thanks a lot.