3 ms·
The guaranteed wraparound of "unsigned" types in C and derivatives is not very helpful. While the "signed" types in C are well defined kinds of integers, which
by adrian_b 3y ago
The guaranteed wraparound of "unsigned" types in C and derivatives is not very helpful.
While the "signed" types in C are well defined kinds of integers, which nonetheless have unpredictable behavior on overflow, the "unsigned" types are ambiguous, because they correspond to 4 different primitive types (each of these 4 being available in various sizes, i.e. 1-bit, 8-bit, 16-bit, 32-bit, 64-bit or 128-bit).
By primitive types I mean types for which the modern CPUs implement distinct dedicated hardware instructions. The 4 types are non-negative integers, integer residues (a.k.a. modular numbers), binary polynomials and Galois-field binary polynomials.
The same operation, e.g. multiplication, is implemented with different algorithms for each of these 4 types.
Moreover, while a 64-bit "unsigned" may be interpreted as a 64-bit non-negative integer or a residue modulo 2^64 or a 64-bit binary polynomial or a value in GF(2^64), there are 2 additional interpretations between which there are subtle differences, as a 64-element array of 1-bit non-negative integers or as a 64-element array of residues modulo-2. The failure to be aware of the differences between the operations that can be performed with these 6 types and using a single name for all can easily lead to bugs.
The wraparound is correct for integer residues modulo 2^N, but it is wrong for non-negative integers, which are more frequent in most applications.
Also the implicit conversions of unsigned types are very bad in C and derivatives. They are some times correct for non-negative integers, but they are always wrong for integer residues. While a small-size non-negative integer may be converted without losses to a bigger size, for integer residues the reverse is true, they can be converted correctly only towards smaller sizes.
Therefore, the unsigned types of C are defined wrongly both when interpreted as non-negative integers and when interpreted as integer residues. Most other languages are not better.
While there are many applications where either non-negative integers, integer residues, binary polynomials or Galois-field binary polynomials are needed, so unsigned C types must be used for lack of a better alternative, the use of "unsigned" types requires extra care in comparison with using the signed types (e.g. all implicit conversions must be avoided) and it must be clearly documented what kind of "unsigned" is really meant (preferably by defining dedicated types for the various possible interpretations; in C++ it is possible to also define correct operations with them, replacing the built-in operators with undesirable behavior).
- n_plus_1_acc 3y agoVery interesting thoughts. I have also seen one programming languages, ehich I cannot find anymore, which doesn't differentiate between signed and unsigned integers as types. Instead, there are just various sized integers, and for each operation you must choose between signed and unsigned semantics. Kind of like Javas >>> and unsignedToString.
- uecker 3y agoI am not sure I follow. unsigned types in C are residues and not binary polynoms or Galois fields (also you can of course store them in unsigned integers). The conversions work, e.g. conversion to a smaller unsigned type are reduced. That some other conversion work does seem convenient to me and not a problem. One can, of course, define types in C for Galois fields and access them using functions that do the correct operations (and by wrapping it in a struct one can also prevent regular operations to be used on such type). In C++ one can overload the builtin operators, but I am not terrible sure this is even a good idea.