### RedDreamer's blog

By RedDreamer, history, 7 months ago, ,

Despite I am big fan of bitsets, I don't even know what is the exact time complexity. I think operation OR, XOR and etc. works in $O(\frac{size}{64})$, the explanation is that solutions which used it got AC. But on the other hand, I have read in blogs that there would be $32$ instead of $64$. Please help me, what is the exact time complexity for each function and which factors it depends on and explain work principles.

• +39

 » 7 months ago, # |   +55 GNU libstdc++ represents the bitset by an array of type unsigned long. Using custom invocation you can check that on Codeforces, we have sizeof(unsigned long) == 4, so 4*8=32 bits are handled in one operation and thus we get the bound $O(\frac{\mathrm{size}}{32})$.Note that most modern (64-bit) systems will have sizeof(unsigned long) == 8, indeed yielding $O(\frac{\mathrm{size}}{64})$, so Codeforces is a bit of an exception.
 » 7 months ago, # |   +3 In java, I've seen it's implementation. It's long array(64 bit). so the complexity of iterating over all masks is size/64. You can compute the time complexity of different operations.
 » 7 months ago, # |   -34 Were you actually ignorant of it!? It is oviously, isn't it?
 » 7 months ago, # | ← Rev. 4 →   +26 $O(\frac{size}{64})$ or $O(\frac{size}{32})$ is not the normal way of using big $O$ notation.A better way is to use $O(\frac{size}{w})$ instead of $O(\frac{size}{constnumber})$.Whether $w$ equals to $32$ or $64$ is not important.