5 ms·

Unsigned does not mean "not negative", it means "modular arithmetic". The only few cases you want that are e.g. hash functions, crypto, etc. In all the other c

Unsigned does not mean "not negative", it means "modular arithmetic". The only few cases you want that are e.g. hash functions, crypto, etc. In all the other cases it's a mistake, and the "patterns" shown in this article to circumvent the issues with unsigned just for the sake of using it are extremely ridiculous I think and much less readable than the normal code using signed integers. If you have things that must never be negative, define a type that does that and gives an error (there are many good safe_int examples in C++) whenever an operation gives a negative number as in that case you've already lost and your business logic / input filtering / .... is wrong and needs to be fixed. Anecdotally, I've written a few hundred thousand kloc of c++ so far and I've never ever had a bug due to signed overflow. Unsigned underflow OTOH... I'm just thankful for clang's ubsan to warn on it because of how many issues it caught. For the immense majority of programs you'll never have sizes close to 63 bits anyways since the CPUs we use barely have 52-bits of address space at most (and if you have more you're likely already using 128 bit sizes) > Where unsigned does benefit here is when these are used as indices into an array. The signed behavior will almost certainly produce invalid indices which leads to memory unsafety issues. The unsigned way will never do that, it’ll stay bounded, even if the index it produces is actually wrong. I'd take negative indice over silently wrong indice any day of the week. The first will be caught hyper quickly, the second will send money to the wrong account silently for a couple years before anyone notices and then you're in much deeper issues.

CasperDern 5y ago
> Unsigned does not mean "not negative", it means "modular arithmetic". Unsigned does mean non-negative (or rather no indication of negatives) as the sign of a number is just the positive or negative factor of a number: 1 or -1.
hamburglar 5y ago
The suggestion of using an unsigned loop counter starting at size-1 and decrementing until “i<size” is no longer true starts this article off with a “this is bad advice” flavor to it in my book. If I encountered that code I’d stare at it way longer than necessary because I’d be trying to figure out what cleverness is hidden in the bizarre/backwards way the loop continuation test is written. I don’t know why you’d do this to someone else who has to read your code.
- reallybigballs 5y ago
  reverse iteration seems pretty basic …
- xxs 5y ago
  It's an idiom - obviously very little known, likely less known than comparing floats to themselves being a NaN check. The standard idiom for doing a reverse loop would be: "for (int i = size; i-- > 0; ) ...". As a side benefit it has lower registry pressure. Some folks have issues reading that one as well. Saying all that not being 'unsigned fan', just the popularity of the idioms comes with their use frequency, and given that 'unsigned; is not popular at all...
AnotherGoodName 5y ago
>Unsigned does not mean "not negative", it means "modular arithmetic". Signed is modular arithmetic with an offset. An unsigned char called i can be thought of as "i mod 256" A signed char called i can be thought of as "((i+128) mod 256) - 128" All results for over/underflow hold for 'i' cast into a char if you do the above in both cases. I think the premise of the article is quite reasonable. It's slightly easier to reason about over/underflow for unsigned arithmetic since it's not offset.
- jcelerier 5y ago
  > Signed is modular arithmetic with an offset. it is not, it models integers (Z). The model only works in the bounds of what the platform can offer of course ; when you use "int" you say "this is an integer. In any case I'm supposed to encounter, adding two positive integers will yield a greater positive integer ; if I add numbers so big that my platform cannot represent the sum my program is meaningless anyways". It is very unlike unsigned which models (much more accurately since it's much easier for our computers with finite memory) Z/pZ.
  - AnotherGoodName 5y ago
    Signed and unsigned are actually treated internally the same on computers. The reason you see -2 printed out when you add signed chars -1 and -1 together is because adding 255 and 255 together gives 254 under mod 256. The signed model that allows negative numbers relies on the fact that all numbers on computers are modular arithmetic. So in that sense any argument that unsigned is modular and signed isn't is incorrect. You're better off choosing the one that forces you to consider how the computer actually operates under the hood.
    - jcelerier 5y ago
      > Signed and unsigned are actually treated internally the same on computers. if you are writing code in C or C++ the computer you are programming for is the C / C++ abstract machine. C++ recently sanctified complement-of-two as integer representation, but C does not and supports machines with one's complement representation.
ghusbands 5y ago
> Unsigned does not mean "not negative", it means "modular arithmetic". In which case it has a terrible name. The name clearly indicates that the primary feature is that it is not signed, and the logical conclusion from that is that it is not negative. That said, I agree; using signed types in C/C++ does generally seem safer and a majority of the techniques listed in the article are unsafe, logically confused, and/or inhibit optimisation. Using signed types in languages like C# is also generally more pleasant, because otherwise you end up with a lot of casts just to interact with the base types (like arrays), language features and third-party libraries.
- Noughmad 5y ago
  > The name clearly indicates that the primary feature is that it is not signed, and the logical conclusion from that is that it is not negative. No, the logical conclusion is that since it has no sign, you don't know whether it's positive or negative. Otherwise the name would be "positive" or "non-negative", not "unsigned". And this conclusion would also be correct.
- xxs 5y ago
  >The name clearly indicates that the primary feature is that it is not signed, and the logical conclusion from that is that it is not negative. Years ago, when the names were designated the CPUs didn't even have proper signed instructions. There was a sign flag, and that was all. In that regard the unsigned was the natural CPU sympathetic type.
  - int_19h 5y ago
    And yet the default type for variables and function arguments in C was (before it got deprecated) signed int, not unsigned.
    - xxs 5y ago
      signed/unsigned stuff predates C, though. My (lack of) experience with C came much later, when I had used assembly for 3 different CPUs already, so no recollection of the times.
virtualritz 5y ago
> Unsigned does not mean "not negative", it means "modular arithmetic". It does mean "not negative" in languages with bounds checks. Like Rust.
- whattheactualf3 5y ago
  Is it called "unsigned" though? In Racket (and in mathematics) we call those natural numbers. The very notion of "unsigned" was invented by video game programmers at Bell Labs. In mathematics positive numbers are still signed (they just have a positive sign).
  - gumby 5y ago
    > The very notion of "unsigned" was invented by video game programmers at Bell Labs. PL/I had (has) unsigned integers back in the 60s, picking up the idea from earlier languages. I believe the novel datatype in PL/I was the CHARACTER type; into the 80s I was still programming machines with variable length bytes. In many ways PL/I heralded the current Ordovician stage of programming languages, with the enormous Cambrian flourishing of hardware-specific (and company-specific) languages slowly dying out. Interestingly the only surviving languages older than it, FORTRAN and LISP, are also machine-independent.
  - masklinn 5y ago
    > Is it called "unsigned" though? Yes: https://doc.rust-lang.org/std/primitive.usize.html https://doc.rust-lang.org/std/primitive.usize.html > The pointer-sized unsigned integer type. > In Racket (and in mathematics) we call those natural numbers. Naturals have no upper bound. Most languages don't have naturals, because they do have upper bounds. Languages which do provide naturals (limited by the host machine) usually don't bother with signing segregation, and give you mathematical integers (again limited by the host machine's capabilities).
  - ncmncm 5y ago
    Unsigned types are supported in machine language. Any language that offers access to features of the machine will support unsigned numeric types. No language supports natural numbers. The best you can get is bignums. A language that calls its numbers natural is just lying. (Likewise, integers, and reals.) "int" is not a lie, it is a hint.
quelsolaar 5y ago
Interesting perspective. I dont have the same experience. To me a wraping 32 bit index on a 64bit machine is much more likely to seg fault if it reads 4 billion values forward, rather than a few bytes backwards and therefore i find unsigned index wrapps to be easier to debug. In all fairness wrapping indicies are an extremely rare bug for me, so i cant say i have much experience debugging it.
- jcelerier 5y ago
  > In all fairness wrapping indicies are an extremely rare bug for me, so i cant say i have much experience debugging it. Do you run your code with -fsanitize=undefined -fsanitize=integer ?
  - quelsolaar 5y ago
    No I do not. I run ISO conformant C without options.
    - jcelerier 5y ago
      You really should try it on your codebase if you have the occasion
- eterevsky 5y ago
  I think when you use a variable that can have values in the range of millions, it's prudent to use 64-bit types and not 32-bit unless you are very much memory-constrained. And I've never seen a 64-bit signed variable overflow.
kazinator 5y ago
Unsigned means "modular arithmetic with a modulus that you do not choose and that is implementation-defined unless you have pinned down the bit width of the unsigned type, and that has implicit conversions from signed types that drastically alter the value". Note that when mathematicians work in the area of congruences, they do not use unsigned integers. For instance, when we look at Euler's Theorem: https://en.wikipedia.org/wiki/Euler%27s_theorem https://en.wikipedia.org/wiki/Euler%27s_theorem all the quantities in the formula can be understood as just integers, not unsigned integers. The exponentiation of a can be understood as regular exponentiation. The modularity plays out in the triple-equal-sign operator and the (mod n) parenthetical part which says that the two sides of the equation are equivalent in a particular way. The left side of the equation uses ordinary exponentiation and can produce values >= n; it is not wrapped. It's crystal clear that we cannot replace the triple equal sign with the regular one, and drop the (mod n).
- SAI_Peregrinus 5y ago
  They also don't use signed integers, in the sense that computer languages use the term. Signed integers are also bounded in extent, and for most systems wrap on over/underflow. Euler's Theorem doesn't hold for them any more than it does for unsigned integers. Don't treat computer "integers" like mathematical integers. It leads to pain. They're members of a few finite fields.

CasperDern 5y ago

> Unsigned does not mean "not negative", it means "modular arithmetic". Unsigned does mean non-negative (or rather no indication of negatives) as the sign of a number is just the positive or negative factor of a number: 1 or -1.

hamburglar 5y ago

The suggestion of using an unsigned loop counter starting at size-1 and decrementing until “i<size” is no longer true starts this article off with a “this is bad advice” flavor to it in my book. If I encountered that code I’d stare at it way longer than necessary because I’d be trying to figure out what cleverness is hidden in the bizarre/backwards way the loop continuation test is written. I don’t know why you’d do this to someone else who has to read your code.

reallybigballs 5y ago
reverse iteration seems pretty basic …
xxs 5y ago
It's an idiom - obviously very little known, likely less known than comparing floats to themselves being a NaN check. The standard idiom for doing a reverse loop would be: "for (int i = size; i-- > 0; ) ...". As a side benefit it has lower registry pressure. Some folks have issues reading that one as well. Saying all that not being 'unsigned fan', just the popularity of the idioms comes with their use frequency, and given that 'unsigned; is not popular at all...

AnotherGoodName 5y ago

>Unsigned does not mean "not negative", it means "modular arithmetic". Signed is modular arithmetic with an offset. An unsigned char called i can be thought of as "i mod 256" A signed char called i can be thought of as "((i+128) mod 256) - 128" All results for over/underflow hold for 'i' cast into a char if you do the above in both cases. I think the premise of the article is quite reasonable. It's slightly easier to reason about over/underflow for unsigned arithmetic since it's not offset.

jcelerier 5y ago
> Signed is modular arithmetic with an offset. it is not, it models integers (Z). The model only works in the bounds of what the platform can offer of course ; when you use "int" you say "this is an integer. In any case I'm supposed to encounter, adding two positive integers will yield a greater positive integer ; if I add numbers so big that my platform cannot represent the sum my program is meaningless anyways". It is very unlike unsigned which models (much more accurately since it's much easier for our computers with finite memory) Z/pZ.
- AnotherGoodName 5y ago
  Signed and unsigned are actually treated internally the same on computers. The reason you see -2 printed out when you add signed chars -1 and -1 together is because adding 255 and 255 together gives 254 under mod 256. The signed model that allows negative numbers relies on the fact that all numbers on computers are modular arithmetic. So in that sense any argument that unsigned is modular and signed isn't is incorrect. You're better off choosing the one that forces you to consider how the computer actually operates under the hood.
  - jcelerier 5y ago
    > Signed and unsigned are actually treated internally the same on computers. if you are writing code in C or C++ the computer you are programming for is the C / C++ abstract machine. C++ recently sanctified complement-of-two as integer representation, but C does not and supports machines with one's complement representation.

ghusbands 5y ago

> Unsigned does not mean "not negative", it means "modular arithmetic". In which case it has a terrible name. The name clearly indicates that the primary feature is that it is not signed, and the logical conclusion from that is that it is not negative. That said, I agree; using signed types in C/C++ does generally seem safer and a majority of the techniques listed in the article are unsafe, logically confused, and/or inhibit optimisation. Using signed types in languages like C# is also generally more pleasant, because otherwise you end up with a lot of casts just to interact with the base types (like arrays), language features and third-party libraries.

Noughmad 5y ago
> The name clearly indicates that the primary feature is that it is not signed, and the logical conclusion from that is that it is not negative. No, the logical conclusion is that since it has no sign, you don't know whether it's positive or negative. Otherwise the name would be "positive" or "non-negative", not "unsigned". And this conclusion would also be correct.
xxs 5y ago
>The name clearly indicates that the primary feature is that it is not signed, and the logical conclusion from that is that it is not negative. Years ago, when the names were designated the CPUs didn't even have proper signed instructions. There was a sign flag, and that was all. In that regard the unsigned was the natural CPU sympathetic type.
- int_19h 5y ago
  And yet the default type for variables and function arguments in C was (before it got deprecated) signed int, not unsigned.
  - xxs 5y ago
    signed/unsigned stuff predates C, though. My (lack of) experience with C came much later, when I had used assembly for 3 different CPUs already, so no recollection of the times.

virtualritz 5y ago

> Unsigned does not mean "not negative", it means "modular arithmetic". It does mean "not negative" in languages with bounds checks. Like Rust.

whattheactualf3 5y ago
Is it called "unsigned" though? In Racket (and in mathematics) we call those natural numbers. The very notion of "unsigned" was invented by video game programmers at Bell Labs. In mathematics positive numbers are still signed (they just have a positive sign).
- gumby 5y ago
  > The very notion of "unsigned" was invented by video game programmers at Bell Labs. PL/I had (has) unsigned integers back in the 60s, picking up the idea from earlier languages. I believe the novel datatype in PL/I was the CHARACTER type; into the 80s I was still programming machines with variable length bytes. In many ways PL/I heralded the current Ordovician stage of programming languages, with the enormous Cambrian flourishing of hardware-specific (and company-specific) languages slowly dying out. Interestingly the only surviving languages older than it, FORTRAN and LISP, are also machine-independent.
- masklinn 5y ago
  > Is it called "unsigned" though? Yes: https://doc.rust-lang.org/std/primitive.usize.html https://doc.rust-lang.org/std/primitive.usize.html > The pointer-sized unsigned integer type. > In Racket (and in mathematics) we call those natural numbers. Naturals have no upper bound. Most languages don't have naturals, because they do have upper bounds. Languages which do provide naturals (limited by the host machine) usually don't bother with signing segregation, and give you mathematical integers (again limited by the host machine's capabilities).
- ncmncm 5y ago
  Unsigned types are supported in machine language. Any language that offers access to features of the machine will support unsigned numeric types. No language supports natural numbers. The best you can get is bignums. A language that calls its numbers natural is just lying. (Likewise, integers, and reals.) "int" is not a lie, it is a hint.

quelsolaar 5y ago

Interesting perspective. I dont have the same experience. To me a wraping 32 bit index on a 64bit machine is much more likely to seg fault if it reads 4 billion values forward, rather than a few bytes backwards and therefore i find unsigned index wrapps to be easier to debug. In all fairness wrapping indicies are an extremely rare bug for me, so i cant say i have much experience debugging it.

jcelerier 5y ago
> In all fairness wrapping indicies are an extremely rare bug for me, so i cant say i have much experience debugging it. Do you run your code with -fsanitize=undefined -fsanitize=integer ?
- quelsolaar 5y ago
  No I do not. I run ISO conformant C without options.
  - jcelerier 5y ago
    You really should try it on your codebase if you have the occasion
eterevsky 5y ago
I think when you use a variable that can have values in the range of millions, it's prudent to use 64-bit types and not 32-bit unless you are very much memory-constrained. And I've never seen a 64-bit signed variable overflow.

kazinator 5y ago

Unsigned means "modular arithmetic with a modulus that you do not choose and that is implementation-defined unless you have pinned down the bit width of the unsigned type, and that has implicit conversions from signed types that drastically alter the value". Note that when mathematicians work in the area of congruences, they do not use unsigned integers. For instance, when we look at Euler's Theorem: https://en.wikipedia.org/wiki/Euler%27s_theorem https://en.wikipedia.org/wiki/Euler%27s_theorem all the quantities in the formula can be understood as just integers, not unsigned integers. The exponentiation of a can be understood as regular exponentiation. The modularity plays out in the triple-equal-sign operator and the (mod n) parenthetical part which says that the two sides of the equation are equivalent in a particular way. The left side of the equation uses ordinary exponentiation and can produce values >= n; it is not wrapped. It's crystal clear that we cannot replace the triple equal sign with the regular one, and drop the (mod n).

SAI_Peregrinus 5y ago
They also don't use signed integers, in the sense that computer languages use the term. Signed integers are also bounded in extent, and for most systems wrap on over/underflow. Euler's Theorem doesn't hold for them any more than it does for unsigned integers. Don't treat computer "integers" like mathematical integers. It leads to pain. They're members of a few finite fields.