Bit Counting from 0 ~ N in O(logn)

Question

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.

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

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) ;
}

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

You don't understand how the function is doing what its doing OR how is its complexity O(logn)? — Ozair Kafray, May 09 '12 at 19:32
He's not understanding the logic; that is, he doesn't know what logic is. Thus, he's unable to logically explain what he doesn't understand. [sarcasm off] — , May 09 '12 at 19:33
I understand why is O(logn), I don't know how this algorithm work. Why if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ; return ((long long)a + 1) / 2 + 2 * solve(a / 2) ; — etlds, May 09 '12 at 19:40
@KerrekSB If its provided a number e.g., 3 it is supposed to count the number of 1 bits from 1-3, so it should be 4 I guess. — Ozair Kafray, May 09 '12 at 19:40
Counting the 1 bits. solve(3) = 0(0) + 1(1) + 1(2) + 2(3) = 4 — etlds, May 09 '12 at 19:42
For logic, look at this answer: http://stackoverflow.com/a/7943292/365188 — Ozair Kafray, May 09 '12 at 20:02

score 2 · Answer 1 · answered May 09 '12 at 19:57

I'll take a stab at the O(lg n) complexity. Note that I don't quite understand what the function does though the proof should still hold on the running time.

Given our recurrence relationship:

T(a) = 0, if a == 0
     | T(a - 1) + O(1), if a is divisible by 2
     \ O(1) + T(a/2)

I'll use the iterative method here:

T(a) = T(a/2) + O(1)
T(a) = T(a/2^2)) + O(1) + O(1)
T(a) = T(a/2^k)) + (k-1)O(1)
// continue unrolling until we reach the base case
T(a) = 0 + O(1) + ... + O(1) + O(1) = kO(1)
// k here corresponds to lg a since we continued dividing the problem set in half
T(a) = (lg a)*O(1)
T(a) = lg a

Q.E.D.

Bit Counting from 0 ~ N in O(logn)

1 Answers1