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
Unable to parse markup [type=CF_MATHJAX]
, the explanation is that solutions which used it got AC. But on the other hand, I have read in blogs that there would beUnable to parse markup [type=CF_MATHJAX]
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.
GNU libstdc++ represents the bitset by an array of type
unsigned long. Using custom invocation you can check that on Codeforces, we havesizeof(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.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.
Were you actually ignorant of it!? It is oviously, isn't 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.