14

I searched around and could not find the performance time specifications for bitset::count(). Does anybody know what it is (O(n) or better) and where to find it?

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

2
  • 2
    What Tomalak mentioned (but failed to explain because he's apparently insecure and needs to assert his knowledge over others) is that STL (Standard Template Library) is an ambiguous term. Some of us in the C++ community have expanded on this in the info-wiki for the tag, which should clarify the source Tomalak's comment. In short, you should just say "standard library" or "stdlib", but we'll know what you mean when you say STL.
    – GManNickG
    Jan 14, 2011 at 18:18
  • 2
    @GMan: No need for personal attacks. They are not welcome here on StackOverflow. Please adjust your tone in the future. Jan 18, 2011 at 12:15

5 Answers 5

12

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.

3
  • 2
    That's not a specification though! :P Jan 14, 2011 at 17:17
  • 3
    @tomalak-geretkal In the gcc implementation, this is O(n). We conclude the specification doesn't require it better than O(n). And nobody would be so stupid to implement it in a way worse than that. We can then safely assume that it's always at least O(n). Possibly better but you can never count on that.
    – Haozhun
    Jan 14, 2011 at 17:21
  • 1
    @Gene: Whilst in this case I happen to agree, this doesn't strictly answer the original question of what the performance specifications are. However, it's a good deduction. Jan 14, 2011 at 17:25
1

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.

3
  • Can you share what other things does STL refer to in the context of C++?
    – yasouser
    Jan 14, 2011 at 18:09
  • 4
    Same comment as I gave you here. There's a time for pedantry, this isn't it. Comment on the question if you want to clarify OP's use of "STL", but don't make it part of your answer and feign that you're somehow incapable of understanding what he meant, it's arrogant and pretentious. Explain things to the OP, don't just say "I can't possibly get this, it's not strictly defined!"
    – GManNickG
    Jan 14, 2011 at 18:15
  • 1
    @GMan I would have thought pointing out that his question was vague and then providing an answer for BOTH of the two things that he could have been asking about will suffice. I don't see how declaring that I cannot do something is "arrogant"; read a dictionary. And it's not as if my entire answer was "I don't know what you mean, try again". Jan 15, 2011 at 15:13
0

"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/

4
  • 2
    This may well be accurate, but just a warning here that cplusplus.com is well-known to be riddled with errors. Jan 14, 2011 at 17:13
  • 2
    Moreover, that would be a description of a certain implementation. Jan 14, 2011 at 17:18
  • @DavidThornley: Indeed, cplusplus.com is very confusing (dare I say, confused?) about the library in general. It uses the term "STL" clearly insinuating that it really means the C++ Standard Library, but then people on the forums talk about the actual STL. Jan 14, 2011 at 17:20
  • thanks for the link. I did see it before posting the question, but it lacked pointers to any clear specification.
    – yasouser
    Jan 14, 2011 at 18:08
0

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.

1
  • 3
    The STL does typically require certain levels of asymptotic performance (big-O). Jan 14, 2011 at 17:15
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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