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.

Improve this question
1
  • Try single-stepping through the code in your favourite IDE/debugger. Commented May 10, 2012 at 15:09

1 Answer 1

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.