Menu
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.
756
bitset::count() is an inbuilt STL in C++ which returns the number of set bits in the binary representation of a number. Parameter: The function accepts no parameter. Return Value: The function returns the number of set bits.
Answer: It is not.
Let's implement bitset in C++, such that following operations can be performed in stated time complexities : init(int size): initializes a bitset of size number of 0 bits. void fix(int pos): Change the bit at position pos to 1.
Bitset represents a fixed-size sequence of N bits and stores values either 0 or 1. Zero means value is false or bit is unset and one means value is true or bit is set. Bitset class emulates space efficient array of boolean values, where each element occupies only one bit.
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.
64
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.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
