Bit Counting from 0 ~ N in O(logn)
<p>The following is the C++ code I saw on interview street website which counting the 1's bit from 0 ~ a (input number), we can say is 1 ~ a though because 0 has no 1s. This code's time complexity is O(logn) using recurrence.</p>

<p>I just don't understand the logic. Can anybody explain why? Thx! </p>

<pre><code>long long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
 return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
}
</code></pre>

<p>BTW __builtin_popcount() is a built-in method that GNU provided for counting the bit which is 1. </p>
