• Forum
  • Lounge
  • Why does there has no complexities for b

 
 
Why does there has no complexities for bitset?

A question.
It is a fixed size collection of bits (size is known at compile time); the library/compiler can (and is expected to) optimise it heavily. Therefore, the time complexity as a function of the logical number of bits in the bitset depends on the available processor instructions and the register size of the hardware platform (the standard can't really provide a complexity specification/guarantee based on the number of bits in the bitset; it's too implementation dependant)

For instance, x86_64, g++ 7.3, -O3 -march=native :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bitset>

///////////////  same complexity for all of these : ///////////////
/////////////// one xor + one popcnt ///////////////////////////
std::size_t foo24( std::bitset<24> bs ) { return bs.count() ; }

std::size_t foo32( std::bitset<32> bs ) { return bs.count() ; }

std::size_t foo48( std::bitset<48> bs ) { return bs.count() ; }

std::size_t foo64( std::bitset<64> bs ) { return bs.count() ; }


///////////////  same complexity for these : ///////////////
/////////////// one xor + two popcnt + one add ///////////////////////////
std::size_t foo96( std::bitset<96> bs ) { return bs.count() ; }

std::size_t foo128( std::bitset<128> bs ) { return bs.count() ; }


///////////////  same complexity for these : ///////////////
/////////////// three xor + three popcnt + two add ///////////////////////////
std::size_t foo160( std::bitset<160> bs ) { return bs.count() ; }

std::size_t foo192( std::bitset<192> bs ) { return bs.count() ; }


// etc 

https://godbolt.org/g/XTekau
Thanks for replying. I've learnt a lot from it.
Registered users can post here. Sign in or register to post.