Comment by jcelerier | Hacker News Reader

Comment by jcelerier | Hacker News Reader

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.

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.

reverse iteration seems pretty basic …

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

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

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

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

And yet the default type for variables and function arguments in C was (before it got deprecated) signed int, not unsigned.

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.

If you mean the default being signed, it's there because B - the predecessor of C - only had a signed integer (machine word) type. But note that this is about the case when the variable has no type at all - e.g. "auto x" is a signed int. They still had the choice of "int x" being equivalent to either "signed int" or "unsigned int" by default, though - since there's no backwards compatibility issue there - and chose signed.

FWIW, signed seems to be the default for most other languages from that time period, and often the only option - e.g. Algol-60 didn't have unsigned integers at all. Pascal kinda sorta did, if you defined an integer subtype with 0 as the lower bound... but the upper would still be that of signed int, and it'd behave as such. And Algol-68 called its unsigned type BITS - a pretty strong hint that they didn't think of it as arithmetic.

I'm actually kinda curious now as to when the concept of unsigned integers first appeared in a high-level programming language first.

Signed also tends to mean modular arithmetic. It's just with a different definition of modular arithmetic than the Euclidean one. See Boute's 1992 paper "The Euclidean Definition of the Functions div and mod" [1] for details on the various definitions.

Both signed and unsigned arithmetic are using finite fields, instead of Abelian rings as most people expect.

[1] https://biblio.ugent.be/publication/314490/file/452146.pdf

> Both signed and unsigned arithmetic are using finite fields,

This is not correct. They are rings with some additional (not mathematically standard) operations thrown in.

'Finite field' means something very specific, and quite different. https://en.wikipedia.org/wiki/Finite_field

Computer integer arithmetic hardware can be used to implement finite field arithmetic, but even the 2^n case takes quite a bit of trickery. https://en.wikipedia.org/wiki/Finite_field_arithmetic

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.

> 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 ?

No I do not. I run ISO conformant C without options.

You really should try it on your codebase if you have the occasion

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.

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

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

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.

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

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

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.

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

> C++ recently sanctified complement-of-two as integer representation

While that's true, signed integer overflow on arithmetic operations remains undefined behavior.

One's complement is on its way out in C too. The next C standard will require two's complement.

> Unsigned does not mean "not negative", it means "modular arithmetic".

It does mean "not negative" in languages with bounds checks. Like Rust.

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

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

> Is it called "unsigned" though?

Yes: 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).

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.

Though, in idiomatic Rust I did not find the use of unsigned as mentioned in the article, signed for indexes is the norm.

> in idiomatic Rust I did not find the use of unsigned as mentioned in the article, signed for indexes is the norm

Huh? If you write things[n] in Rust, and n isn't usize that's an error, you can't index things with the other primitive types at all out of the box.

Wait, what?

Pretty much everything for indices (at least in the stdlib) seems to be 'usize' in my experience (i.e. Vec), which is unsigned.

Am I missing something?

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

Reply on news.ycombinator.com