| 37 | /** Count the number of bits set in an unsigned integer type. */ |
| 38 | template<typename I> |
| 39 | unsigned inline constexpr PopCount(I v) |
| 40 | { |
| 41 | static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2); |
| 42 | constexpr auto BITS = std::numeric_limits<I>::digits; |
| 43 | // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation. |
| 44 | // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64. |
| 45 | if constexpr (BITS <= 32) { |
| 46 | v -= (v >> 1) & 0x55555555; |
| 47 | v = (v & 0x33333333) + ((v >> 2) & 0x33333333); |
| 48 | v = (v + (v >> 4)) & 0x0f0f0f0f; |
| 49 | if constexpr (BITS > 8) v += v >> 8; |
| 50 | if constexpr (BITS > 16) v += v >> 16; |
| 51 | return v & 0x3f; |
| 52 | } else { |
| 53 | static_assert(BITS <= 64); |
| 54 | v -= (v >> 1) & 0x5555555555555555; |
| 55 | v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333); |
| 56 | v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f; |
| 57 | return (v * uint64_t{0x0101010101010101}) >> 56; |
| 58 | } |
| 59 | } |
| 60 | |
| 61 | /** A bitset implementation backed by a single integer of type I. */ |
| 62 | template<typename I> |