Why is C++20's `std::popcount` restricted to unsigned types?

Question

The functions from P0553R4: Bit operations are constrained to only work on unsigned integers. The proposal does not give a reason for this constraint. I can see that this makes sense if the bit representation of a signed integer is not defined, but with C++20, we are guaranteed that signed integers use two's complement.

To me, it thus seems reasonable to allow e.g. std::popcount to be called with a signed integer type, as an implementation could simply cast to the corresponding unsigned type to do the bit-operation in the unsigned domain.

What is the reason for P0553R4 to add this constraint? (Is it simply missing synchronization between P0553R4 and P0907R4?)

When applying bitwise operations, such as counting the number of set bits (popcount), on signed integers, there can be unexpected behavior due to the sign bit. Specifically, the sign bit can propagate during operations, potentially leading to incorrect results or undefined behavior. — Eldinur the Kolibri, Jun 05 '23 at 14:02
It looks like this has been a convention, in GCC and MSVC at least, for builtin (extension) implementation of similar functions: https://learn.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-170 and https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html — buer, Jun 05 '23 at 14:03
`template int spopcount(T s) { return popcount(static_cast>(s)); }` ... but anyway, I presume the P0553 proposal itself predates the 2s complement representation as an independent proposal. Something that could be easily "fixed" with a new small proposal. Proposals like that need someone to propose them. — Eljay, Jun 05 '23 at 14:13
Even with the two's complement guarantee in C++20, signed integer overflows still have UB in C++20. Perhaps the reasons for the `` family of functions only working with unsigned types can be found in the reasoning behind that decision? — Ted Lyngmo, Jun 05 '23 at 14:18
Signed integer types have been two's compl. since c++17. This isn't something new. The reason their overflow is UB is optimization. Compilers assume that `i < i+1` is always true. For unsigned integers they can't because overflow is not UB. — doug, Jun 05 '23 at 14:36
What is the use case for counting bits in signed values? All recommendations for using bitmasks are to always use unsigned. And on the odd chance that you find a use case, you can easily do the casting yourself. — BoP, Jun 05 '23 at 14:57
@doug _"Signed integer types have been two's compl. since c++17"_ - The standard didn't require signed integer types to be two's complement before C++20. — Ted Lyngmo, Jun 05 '23 at 15:05
While technically possible, I speculate that the use of `std::popcount` on signed values is very limited. Quick quiz: what would the value of `std::popcount(-1)` be? If you think you know the value, you are already wrong. — Drew Dormann, Jun 05 '23 at 16:24
@TedLyngmo Yep, sorry You're right. It was implementation defined in c++17. I never saw any that weren't and their behavior wasn't changed in c++20. Probably how I got the notion it was part of c++17. Thanks for correcting that. — doug, Jun 05 '23 at 16:40
another footgun example - `int16_t a = -1, b = -2; std::popcount(a+b)` - not well-defined — M.M, Jun 06 '23 at 08:41
Also note: C++20 also introduces `std::bit_cast<...>(...)`—a standard-compliant, `constexpr` way to reinterpret bits, making doing the Right Thing here easy. — geometrian, Jun 08 '23 at 05:53

score 71 · Accepted Answer · answered Jun 05 '23 at 15:11

71

Pretty simple: Implicit widening conversions on unsigned types do not change the result. Implicit widening conversions on signed types (including promotions) perform sign-extension, which does change the result if the input was negative.

Having an operation whose result becomes incorrect due to integer promotion definitely falls into the "foot cannon" category.

You can still feed (bit patterns representing) negative values to popcount, but you have to take control of the conversion sequence, which helps you get the result you expect.

answered Jun 05 '23 at 15:11

Ben Voigt

277,958
43
419
720

1

Is there anything in the proposals leading up to the C++20 standard that also gives this motivation? I know it's pretty hard to answer a language-lawyer question to motivate why something _isn't_ in the standard, but perhaps, in this case, it can be found in the proposals? – Ted Lyngmo Jun 05 '23 at 15:16
6

@TedLyngmo: [tag:language-lawyer] simply isn't appropriate for a "why?" question so I ignored it. I haven't gone looking in the proposal, since OP indicates he's already done so. – Ben Voigt Jun 05 '23 at 15:20
5

The same argument can be made for `std::countl_zero` with unsigned types – Artyer Jun 05 '23 at 21:14
1

@Artyer: That is true. Maybe it could be solved by having the programmer pass the width of the type in bits as an explicit template argument? That would make it somewhat more difficult to write generic code though. – Ben Voigt Jun 05 '23 at 21:42
6

@Artyer: Having `countl_zero(int)` not be a valid overload means that `countl_zero(x+1)` is an error for narrow unsigned `x` that promotes to signed `int` for `+` (https://godbolt.org/z/WGvx644h5), so you realize you need `static_cast`. BTW, even with signed types, the leading-zero count still changes when widening for non-negative integers. Also, it's the source type not the destination that determines whether zero- or sign-extension happens, so for `int x`, `popcount(x | 1uLL)` or `countl_zero(x | 1uLL)` will sign-extend to 64-bit (or whatever unsigned long long is). – Peter Cordes Jun 06 '23 at 04:49
1

Loved the foot cannon comment. Hadn't seen that before and will be borrowing it in the future. – Michael Dorgan Jun 06 '23 at 21:44
2

@BenVoigt: Alternatively, define a function that reports the index of the highest non-zero bit (which would e.g. by 6 for values in the range 64 to 127, inclusive, regardless of the size of the type involved). – supercat Jun 06 '23 at 22:12
3

@supercat: Commonly known as "log2()" Without a special instruction, see https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog – Ben Voigt Jun 06 '23 at 22:14
1

@BenVoigt: log2() would only return 6.0 for an input value of 64.0. Truncating its value to an integer might work, but would on many platforms likely be slower than code to find the bit position of the highest set bit. – supercat Jun 06 '23 at 22:16
4

@supercat: I'm not saying that you should call "log(x)/log(2.0)` to find the position of the highest non-zero bit, I'm saying that the function you are proposing is already named -- you have an efficient integer `log2()` – Ben Voigt Jun 06 '23 at 22:20
1

Arguably the popcount of a negative integer is infinity. Just like there are infinitely many elided 0 bits in a non-negative one, there are infinitely many elided 1 bits in a negative one. :-) – R.. GitHub STOP HELPING ICE Jun 07 '23 at 18:02
@R..GitHubSTOPHELPINGICE: If the limit as ALU busses becomes wider and wider approaches "arbitrary-precision integer", then sure, promotion to an arbitrary-precision integer should have unbounded sign-extension bits. – Ben Voigt Jun 07 '23 at 18:07
2

@supercat: index of highest-set bit is what x86's `bsr` instruction produces. To use it for `__builtin_clz(unsigned int)`, GCC does `xor eax, 31`. https://godbolt.org/z/vqsKWsjfx (Since the builtin (like the instruction), doesn't produce normal results when the input is zero, it doesn't ever have to generate a `32` like it does with C++20 `countl_zero`.) But yeah, if you want the MSB-index aka ilog2 yourself, you need to undo the `31-clz` or `31^clz` yourself, and rely on compilers optimizing back to just a `bsr` instruction (or `31-lzcnt` if available since that's faster on AMD.) – Peter Cordes Jun 07 '23 at 20:02
2

Anyway, sometimes MSB-index is what you actually want, and it's inconvenient not to have a function for that, instead having to come up with a way to do it that's correct everywhere but which compilers can optimize down to a single instruction. Intrinsic for `bsr`/`bsf` specifically are less portable than for the newer `lzcnt` / `tzcnt`, and you don't necessarily want to restrict yourself to that anyway, instead letting a compiler choose `lzcnt` if optimizing for AMD. – Peter Cordes Jun 07 '23 at 20:04

score 25 · Answer 2 · edited Jun 29 '23 at 01:01

popcount counts bits, and hence takes a type intended for use as a "bit container".

unsigned integer types are intended for use as bit containers (or modulo-2^n values).
signed integer types are intended for use as numbers, somewhat more abstractly.

Yes, it's true that since C++20, twos-complement semantics are guaranteed for signed integers, but that's a non-essential detail - which is exactly why two's-complement wasn't guaranteed until C++20. And if you're not a language-lawyer, you are likely to not even be aware of this change.

So, instead of trying to be a language-lawyer/human encyclopedia - make less assumptions about the exact semantics of types which may have been defined otherwise. If you make such assumptions - you might luck out and popcount correctly; but you might just get bitten by @BenVoigt's answer.

_{See also the application of the same principle in my answer to this question.}

score -2 · Answer 3 · answered Jul 02 '23 at 05:51

The reason why popcount in C++20 is restricted to unsigned types is to ensure consistent behavior and avoid potential pitfalls when working with signed integers.

When applying bitwise operations, such as counting the number of set bits (popcount), on signed integers, there can be unexpected behavior due to the sign bit. The sign bit can propagate during operations, potentially leading to incorrect results or undefined behavior.

To ensure consistent and predictable behavior, the decision was made to restrict popcount to unsigned types. Unsigned integer types are intended for use as bit containers, while signed integer types are intended for use as numbers. By restricting popcount to unsigned types, it avoids potential pitfalls and ensures that the function behaves as expected in all cases.

Why is C++20's `std::popcount` restricted to unsigned types?

3 Answers3