2

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.

interjay
  • 107,303
  • 21
  • 270
  • 254
xueliang liu
  • 556
  • 3
  • 13

1 Answers1

2

Suppose you have the number n = 2X+1 and you want to find 

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

This is equal to:

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

Since count(2j+1) = count(2j)+1 and count(2j) = count(j), you can simplify to:

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

Which is your recurrence relation.

If n is even (and thus not of the form 2X+1), you can use the formula 

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

which follows directly from the definition of solve as a sum above.

interjay
  • 107,303
  • 21
  • 270
  • 254