Problem statement:

I have a string consisting of 0 and 1's only, say "000100101100". I want to count how many 0's are there in the string "efficiently".

Let n = length of the string. Then obviously we have O(n) algorithm.

My string will have more 0's than 1's; i.e., at least n/2+1 chars will be 0's.

My question is:

Can we do better, say O(lg n)?

No, I don't know if it is possible to achieve O(lg n) running time. I am just asking for help.

thanks for your idea about bitset.

I did consider the bitset template for a while. But then I found it is not appropriate for my problem:

I want to use a long string s of length 10 million to represent the prime numbers less than 10 million.

You see that the string has lots of 0's (s[i]=='0' if i is not prime, otherwise, s[i]== '1').

Even if you can use bitset, I don't know how efficient the count() function of bitset is. My guess is that it would be O(n).