Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this little exercise:

for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      foo ();

(j <<= 1 means j = (j << 1), where << is the bitwise left shift operator. & is the bitwise and operator.)

I am supposed to determine how many times will the foo function be called for some n. The result should be both an exact number (or the most accurate approximation possible) and asymptotic (like O(n)).

share|cite|improve this question

migrated from Sep 22 '12 at 22:56

This question came from our site for professional and enthusiast programmers.

Suggestion: you could try compiling and running the code with a few different values of n, just to get a feel for how the answers should look. – Paul R Jan 12 '12 at 17:29
It's analysis so I should use just pencil and paper. – Machta Jan 12 '12 at 17:35
Running the code is (a) instructive and (b) a useful reality-check against any theoretical answers that you come up with – Paul R Jan 12 '12 at 22:16

The number of foo() calls is the number of 1 bits in all numbers from 0 to $n$ (or all even numbers between $0$ and $2n$ - same thing). Asymptotically, it's $O(n \log n)$, because the number of 1 bits is around $\log_2(n)/2$.

I don't have an exact function. It won't be a smooth function - for example, $f(1023)-f(1022)=10$, but $f(1024)-f(1023)=1.$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.