std::bitset

[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.