Python 3 has unlimited size integers, which can function as dynamic size bitsets when doing bitwise operations. Python is still about 3x slower than C++ bitsets with no pragmas and 10x slower than C++ with avx2+O3 pragmas. However, the Python integers have dynamic size, so there some potential of making a problem that requires dynamic bitsets purely to mess with people who use C++ standard library bitsets.
Anyways, here's some simple code I wrote in Python for https://ecna22.kattis.com/problems/amusicalquestion. It is AC in 0.16s.
Code
AFAIK, there is
std::tr2::dynamic_bitset
in (and I believe, only in) GCC (reference link here). I think it is to replacestd::vector<bool>
in a near future, but it is not yet in the standards. It is at least in a "usable" state if I remember correctly.There's a simple way to use static bitsets (with minimal overhead) when dynamic bitsets are needed.
And if you want to limit $$$N$$$ to a certain limit, you can do it using
std::enable_if
(now you can even usesize_t
without warnings):And if you want to be more space efficient about it, consider replacing
2 * N
bystatic_cast<uint32_t>(1.5 * N + 1)
or something similar everywhere, though the smaller the increase, the more functions andif
checks there will be. In the worst case, if the increase is linear, you'll either have a bloated binary (with potential instruction cache misses) or the compiler will fail to compile the code due to out of memory errors, not to mention the linear search time in this recursive definition.Is this a certified way to do bitset in python?
I found python 1 << k can hold 1000 number of bits. Not sure how to do count, any, iterating all 1's in constant time as C++ ? https://leetcode.com/problems/all-paths-from-source-lead-to-destination/submissions/1458994019/?envType=problem-list-v2&envId=topological-sort
for
count()
, you can do like__builtin_popcount()
in c++ in $$$\mathcal O(\frac{N}{w})$$$:for
any()
just see if it's 0.for iterating all 1s you can use lowbit (count()) times:
any is lowbit, I see. Let me study __builtin_popcount
How to understand 0x0F0F0F0F, 0x5555555 lmao??