jzhe727's blog

Python 3 can do bitsets too
By jzhe727, history, 13 months ago, In English

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
  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
13 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

AFAIK, there is std::tr2::dynamic_bitset in (and I believe, only in) GCC (reference link here). I think it is to replace std::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.

→ Reply
»
13 months ago, # |
  Vote: I like it +29 Vote: I do not like it

There's a simple way to use static bitsets (with minimal overhead) when dynamic bitsets are needed.

template <uint32_t N> // size_t might give stack frame related warnings
void helper(int n) {
    if (n <= N) {
        bitset<N> b;
        std::cout << "N = " << b.size() << '\n'; // implementation goes here
    } else {
        helper<2 * N>(n);
    }
}

void solve(int n) {
    helper<1>(n);
}

And if you want to limit $$$N$$$ to a certain limit, you can do it using std::enable_if (now you can even use size_t without warnings):

static constexpr size_t MAX_BITSET_SIZE = 10000;

template <size_t N>
std::enable_if<(N <= MAX_BITSET_SIZE)>::type helper(int n) {
    if (n <= N) {
        std::bitset<N> b;
        std::cout << "N = " << b.size() << '\n'; // implementation goes here
    } else {
        if constexpr (2 * N <= MAX_BITSET_SIZE) {
            helper<2 * N>(n);
        }
    }
}

void solve(int n) {
  helper<2>(n);
}

And if you want to be more space efficient about it, consider replacing 2 * N by static_cast<uint32_t>(1.5 * N + 1) or something similar everywhere, though the smaller the increase, the more functions and if 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.

→ Reply