Note: All of the information in this blog relies on implementation-defined behavior. Do not use this in production code. In Codeforces contests, it's usually preferred to simply use hand-implemented bitset, because you've infinite time before the contest; or bitset
(however bitset
is printed differently from vector<bool>
in GDB, and it doesn't work if you need dynamic size).
It's mentioned in a previous comment that bitset internal can be accessed by casting it to int32_t*
. What about vector<bool>
?
Method 1: cast its content to uint32_t*
(or uint64_t*
), but it'll only work when _GLIBCXX_DEBUG
is not defined.
vector<bool> a {1,0,0,1,0,1};
cout << * (uint32_t*&&) a << '\n';
cout << * (uint32_t*&&) a.begin() << '\n';
Both prints 41
.
Method 2: Access _M_p
and _M_offset
members of the iterators.
In normal mode it works fine, but in debug mode it will throw this error
error: ‘std::__cxx1998::_Bit_type* std::__cxx1998::_Bit_iterator_base::_M_p’ is inaccessible within this context
In this case, just cast it to the base. If you want something that works with both lvalue and rvalue, you can use
#ifdef _GLIBCXX_DEBUG
__cxx1998::_Bit_iterator_base& PP(auto& x){ return (__cxx1998::_Bit_iterator_base&) x; }
__cxx1998::_Bit_iterator_base&& PP(auto&& x){ return (__cxx1998::_Bit_iterator_base&&) x; }
#else
template<class T>
auto&& /* decltype(auto) ? */ PP(T&& x){ return std::forward<T>(x); }
#endif
(any way to simplify the template?)
#define private public
may work, but I don't recommend using it.
Sample code: computing bitwise AND of two vectors:
vector<bool> a {1,1,0,1,0,1};
vector<bool> b {0,1,1,1,1,0};
transform(
PP(a.begin())._M_p,
PP(a.end())._M_p + (PP(a.end())._M_offset != 0),
PP(b.begin())._M_p,
PP(a.begin())._M_p,
[](auto x, auto y){ return x&y; });
for(int x : a) cout << x;
Don't forget + (T(a.end())._M_offset != 0)
when necessary.
Find the first set bit:
vector<bool> a(100);
a[52] = 1;
auto iter = begin(a);
PP(iter)._M_p = find_if(PP(iter)._M_p, PP(end(a))._M_p, [](auto x){ return x; });
iter = find(iter, end(a), 1);
cout << iter - begin(a) << '\n';
Note: While it's possible to change unused bits like this
vector<bool> a {1,1,0,1,0,1};
*PP(a.begin())._M_p = 0b111111111;
a.resize(7);
for(int x : a) cout << x;
and it would still work fine, I'm not sure if it's always the case. It would simplify the implementation of some algorithm.