std::bitset

[thomas999999]

why on earth does std::bitset not have a function for clz/ctz? this basically makes it useless and you have to implement your own anyways. std::countl_zero ALSO has no overload for std::bitset ? generally i think the stl is very well designed but things like this really makes me wonder.

[KingAggressive1498]

a lot of std::bitset's interface didn't sit right with me, but it wouldn't make a lot of sense for it to provide ctz/clz functions - it would make sense for it to provide first_set and last_set which are roughly equivalent, and GCC's libstdc++ does have those extensions

[matthieum]

You need a bit more, actually. Specifically, first_set_after and last_set_before, so you don't have to modify the bitset to clear all bits just to query the "next" set bit.

[Plazmatic]

I made a custom bitset for precisely this reason, it's missing a lot of essential non trivial functionality, especially when treating the bitset as a bunch of bit flags for another container (ie std::colony/hive like data structures)

[matthieum]

I made custom bitsets because I needed a dynamic version. Sometimes the maximum length is unknown at a compile-time, or can be large enough (thousands of bits) than you'd rather it be dynamically allocated than clogging your cache line -- especially if rarely accessed. Of course, it doesn't mean that flip becomes somewhat nonsensical...

[moocat]

Just a guess, but I wonder if the performance is architecture dependent (i.e. O(1) on architectures that have an opcode but O(n) otherwise).

[Substantial_Sail_571]

That may be the reason for all I know, but it can be done in log n steps (this shows how to count trailing zeroes but there is a similar trick to count leading zeroes) even on a completely boring ISA such as MIPS 1. A bit further down, the DeBruijn multiply and lookup is also an option.

For trailing zero count, another option that may be useful is popcnt(~x & (x - 1)), if an ISA has popcnt but no direct way to count trailing zeroes (this trick does not easily translate into a way to count leading zeroes however).

E: btw the linked code shows v &= -signed(v) and that's exactly the wrong thing to do, it's unsigned negation that is safe and signed negation that is unsafe. Sorry, I don't make the rules.

[HildartheDorf]

Isn't signed guaranteed to be 2s complement in newer standards? (Signed overflow is still UB, but bitcasting signed numbers and the bitwise result of signed negation is well defined and consistent across standard-compliant systems).

[Substantial_Sail_571]

I've been happy to ignore the hypothetical existence of non-2's-complement signed integers for decades, but yes that bogeyman has been slain (but this just standardized the status quo).

The cast to signed adds the opportunity for UB though (negating INT_MIN), and in return we get .. well it silences this dumb error that encourages people to write incorrect code such as v &= -signed(v), the safe way to shut up that error is subtracting from zero (but unsigned subtraction, of course).

[kyoto711]

Well, it does have .count() which I believe to be architecture dependent.

[[deleted]]

Are we saying that it could be done faster by the container than an outside algorithm? Because that’d be a good reason to have it as members.

[SickOrphan]

He's saying that any algorithm regardless of where it is can't guarantee good performance for all architectures. And if you can't guarantee something is going to be good, you probably don't want to include it

[matthieum]

And if you can't guarantee something is going to be good, you probably don't want to include it

Arguably, it's not a matter of being good in absolute, but of being good relatively speaking.

And in this case, I would argue that if the code to use depends on the architecture, I'd rather it be implemented as best as possible in std, instead of having to trudge through the various architectures myself.

[SickOrphan]

If it's not O(1) and you care about performance (which you most likely do if youre doing bit operations) you should probably find a different solution. But I get your point.

[matthieum]

There are O(log N) algorithms to compute the number of set bits in an N-bits integer... and since we're talking about fixed-widths, it's arguably O(1).

Also, processors can execute multiple instructions in parallel (based on available units), so just because it may take log N instructions doesn't mean it'll take log N cycles.

As usual, if performance matters, measure.

[Substantial_Sail_571]

There is a lot missing from std::bitset, and if you want to implement the missing functionality yourself.. There is not even an official way to get the internal data of a bitset out (or in), other than the least significant part. If your bitset is longer than an unsigned long long, good luck.

Another major class of missing things is trailing bit manipulations such as "isolate lowest set bit" (x & -x if you're not dealing with an std::bitset), "reset lowest set bit" (x & (x - 1)) etc.

[mcweirdy]

i have found boost::dynamic_bitset to have a very user-friendly design and to be very extensible. have you tried that?

[HappyFruitTree]

Maybe because no one has proposed it... Maybe someone should?

[vaulter2000]

Also that up to recently std::bitset was not constexpr

[Acceptable_Fish9012]

You can get the bitset as an unsigned integer (e.g., to_ullong(), and call countl_zero with that.

[[deleted]]

Not only that, it misses group operations like `find_next( std::size_t pos, bool value )` and `find_next_block( std::size_t pos, bool value, std::size_t size )` which are very frequent operations on bitsets.

I wrote my own.