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)?

实在想不明白如何才能在不遍历整个串之前得知0的个数，了不起只能判断1的个数，当1的个数到达n-n/2-1时停止遍历，得出0的个数。但是意义也不大。
所以还请你明示！

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

may be you can change the string type to the bitset type and then you could transfer the operation of the bitset type ,just like that:
size_t num=bitvec.cout()//the bitvec is a object of bitset type and the number means that the 1's units;

another way :you can make a use of the iterator to count the 1's units in you string ,for exemple :

#include<iostream>
#include<string>
#include<cstddef>
using namespace std;
int main(){
size_t num0=0,num1=0;
string str("0001111000");
string::iterator iter;
for(iter=str.begin();iter!=str.end();++iter){
if(*iter!=' '){
if(*iter=='1')
num1++;
if(*iter=='0')
num0++;
}
else cout<<"errer!"<<endl;
}
cout<<num1<<endl;
cout<<num0<<endl;
return 0;
}
if you have some problems please show me and give me a reason ,thank you.
by the way ,i see ,i can't make sure that i understand you real idea.

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).