The most efficient method to change the value of a range of bits in std::bitset

Question

I need an efficient method with low complexity to change the values of a range of bits in the bitset :

bitset<1000000> bs;

and I need to set values from 100 to 500 to TRUE for example .

what is the fastest method to accomplish this in the lowest complexity ?

using a loop wouldn't suffice for sure .

I'm voting to close this question as off-topic because SO is not a code writing service, please show your efforts — EdChum, Jun 15 '16 at 08:19
@EbramShehata probably you could provide several attempts and see which is more efficient. — Mine, Jun 15 '16 at 08:33
`std::bitset` does not allow direct access to the stored data, but if you can implement your own bitset class, say using the bits in `uint64` variables, you could set 64 bits in one instruction. — Karsten Koop, Jun 15 '16 at 09:42
note that `bitset<1000000> bs;` has a high chance of causing a stack overflow. I suggest using `auto bs = std::make_unique();` if that troubles you enough. — rubenvb, Jun 15 '16 at 10:12

score 1 · Answer 1 · edited May 23 '17 at 11:52

An ordinary for-loop is the easiest and fastest way:

std::bitset<1000000> bs;

for (unsigned i = start, stop = start + n; i != stop; ++i)
  bs.set(i);

Unfortunately:

given the size of bs, working with masks / shifting isn't an option (e.g. see in bitset, can i use "to_ulong" for a specific range of bits?)
the interface of bitset doesn't support ranges / sub-blocks (e.g. What is the performance of std::bitset?). The same limitation is present in boost::dynamic_bitset.

Also consider that std::bitset doesn't come with iterators, so it cannot be used with the functions in <algorithm> library.

If performance really matters you could consider an ad-hoc implementation.

1 Answers1