nkamzabek's blog

Confusing bitsets
By nkamzabek, history, 5 years ago, In English

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.

  • Vote: I like it
  • +39
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Were you actually ignorant of it!? It is oviously, isn't it?

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +26 Vote: I do not like it

$$$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.

→ Reply