What is the performance of STL bitset::count() method?

I searched around and could not find the performance time specifications for bitset::count(). Does anybo开发者_如何转开发dy know what it is (O(n) or better) and where to find it?

EDIT By STL I refer only to the Standard Template Library.

I read this file (C:\cygwin\lib\gcc\i686-pc-cygwin\3.4.4\include\c++\bitset) on my computer.
See these

/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }      

size_t
_M_do_count() const
{
  size_t __result = 0;
  for (size_t __i = 0; __i < _Nw; __i++)
  __result += __builtin_popcountl(_M_w[__i]);
  return __result;
}

BTW, this is where _Nw is specified:

  template<size_t _Nw>
    struct _Base_bitset

Thus it's O(n) in gcc implementation. We conclude the specification doesn't require it better than O(n). And nobody in their right mind will implement it in a way worse than that. We can then safely assume that it's at worst O(n). Possibly better but you can never count on that.

I can't be sure what you really mean by "STL" here, due to a prevailing misuse of the term in the C++ community.

• The C++ Standard (2003) makes no mandate for the performance of std::bitset::count() (or, in fact, any members of std::bitset as far as I can see).

• I can't find any reference suggesting a mandate for the performance of STL's bitset::count() either.

I think any sane implementation will provide this in constant (or at worst linear) time, though. However, this is merely a feeling. Check yours to find out what you'll actually get.

"SGI's reference implementation runs in linear time with respect to the number of bytes needed to store the bits. It does this by creating a static array of 256 integers. The value stored at ith index in the array is the number of bits set in the value i."

http://www.cplusplus.com/forum/general/12486/

I'm not sure you're going to find a specification for that, since the STL doesn't typically require a certain level of performance. I've seen hints that it's "fast", around 1 cycle per bit in the set's size. You can of course read your particular implementation's code to find out what to expect.

The Algorithm that we follow is to count all the bits that are set to 1. Now if we want to count through that bitset for a number n, we would go through log(n)+1 digits.

For example: for the number 13, we get 1101 as the bitset.

Natural log of 13 = 2.564 (approximately) 3

Number of bits = 3+1 = 4

For any number n(decimal) we loop log(n)+1 times.

Another approach would be the following:

int count_set_bits_fast(int n) {
int count = 0;
while (n > 0) {
    n=(n&(n-1));
    count++
}

return count;
}

If you analyse the functional line n=(n&(n-1)); you shall find that it essentially reduces the number of bits from right to left.

The Order would therefore be number of total set bits.

For example: 13 = 1101

1101&1100 = 1100

1100&1011 = 1000

1000&0111 = 0

O(number of set bits), O(Log(n)+1) Worst case