<p>I'm implementing signed and unsigned integers in my language. They are represented in C as <code>signed long</code> and <code>unsigned long</code> respectively.</p>
<pre><code>struct value {
    enum type type; / SINT, UINT, ... */

    union {
          signed long sint;
        unsigned long uint;
        /* more types... */
    } as;
};
</code></pre>
<p>Basic arithmetic operations such as <code>+</code> and <code>-</code> may operate on integers of mixed signedness depending on the types of the operands:</p>
<pre><code>struct value accumulator, argument;
/* ... */

/* accumulator.type == UINT &amp;&amp; argument.type == SINT */
accumulator.as.unsigned_integer += argument.as.signed_integer;
</code></pre>
<p>This code causes the C compiler to emit warnings like:</p>
<pre><code>warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]
</code></pre>
<p>Which makes me worried about the correctness of this implementation.</p>
<p>I considered simply making it an error to operate on values of mixed signedness. I feel this would make the language too annoying to use though since the programmer would be required to defensively convert the integers every single time.</p>
<p>I currently handle overflows by letting the values wrap around. I assume two's complement integer representation and compile with <code>-fwrapv</code>. I plan to implement overflow checks with transparent promotion to arbitrary precision integers in the future. I want to make integers work seamlessly just like they do in Python and Ruby.</p>
<p>So is there a correct way to implement this? Any pitfalls and footguns I should be considering? How do other languages do it?</p>

<language-design><implementation><c><math><integers>
Correctness of mixed signed/unsigned arithmetic
CC BY-SA 4.0
2023-12-05T19:12:28.943Z
Welcome to PLDI! It might be useful to know how you handle overflow with signed+signed and unsigned+unsigned operations. Whether it's checked, wrapping, or UB might influence the decision for how to handle signed+unsigned
rydwolf
CC BY-SA 4.0
2023-12-05T19:38:11.937Z
@RydwolfPrograms, it's currently wrapping as I assume two's complement integer representation and compile with `-fwrapv` but I plan to implement overflow checks with transparent promotion to arbitrary precision integers in the future, like in Python and Ruby.
Matheus Moreira
CC BY-SA 4.0
2023-12-06T18:34:54.510Z
I would introduce unsigned integers only as a special case of a general feature: User-defined integers with restricted value ranges, the way Ada does it (e.g. `Small_Int` on [this page](https://www.adaic.org/resources/add_content/standards/05rm/html/RM-3-2-2.html)).
Peter - Reinstate Monica
CC BY-SA 4.0
2023-12-10T13:30:04.060Z
You might like to consider having an unnamed union, so that you can then write `x.uint` rather than `x.as.uint`.
Martin Kealey
CC BY-SA 4.0
2023-12-10T18:51:54.473Z
@MartinKealey I've always used unnamed unions but since discovering the `as` idiom I've come to prefer it. Short, correct, reads like natural english, distinguishes union fields from regular types and makes the type punning explicit.
Matheus Moreira
CC BY-SA 4.0
2023-12-10T22:19:14.093Z
The answer to “is there a correct way to implement this?” depends on your choice of integer model. I think a good baseline is [As-if Infinitely Ranged](https://www.researchgate.net/publication/221542289_As-If_Infinitely_Ranged_Integer_Model) (AIR): fixed-precision integer arithmetic is correct when it always either gives the same answer as arbitrary-precision arithmetic would have, or signals an error if that value isn’t representable.
Jon Purdy
<blockquote>
<p>This code causes the C compiler to emit warnings like: [...]
Which makes me worried about the correctness of this implementation.</p>
</blockquote>
<p>Let's examine this with an example:</p>
<pre><code>accumulator.as.unsigned_integer = 2;
argument.as.signed_integer      = -4;

accumulator.as.unsigned_integer += argument.as.signed_integer;
</code></pre>
<p>So then <code>accumulator.as.unsigned_integer</code> will:</p>
<ul>
<li>have an small number, or;</li>
<li>be near to 0xffff...ffff, or;</li>
<li>will trap some math exception?</li>
</ul>
<p>And, with another C compiler, or in another CPU, the reply above will remain?</p>
<hr />
<p>This warning is telling you this code is not portable, because it contains behavior that is not guaranteed to hold (or even exist at all!) by C language standard (a.k.a., undefined behavior).</p>
<p>So yes, you should be worried that mixing signed with unsigned may produce weird results (as above) or produce different results (or no result at all) when compiling this code with another C compiler or in another CPU/architecture.</p>

CC BY-SA 4.0
2023-12-05T22:05:31.680Z
2023-12-06T04:26:31.697Z
2023-12-06T04:26:31.697Z
André L F S Bacci
CC BY-SA 4.0
2023-12-06T18:46:52.337Z
Why would it trap? Unsigned arithmetic in C is well-defined as modulo arithmetic. The result will be correct (if applicable, modulo 2^n) if interpreted as unsigned. It will, interestingly, also be "correct" if interpreted as signed; in the example, the result of the addition modulo 2^n, UINT_MAX-1, has the same bit representation as a signed -2 in 2's complement. In C it's also OK to convert the type through a union.
Peter - Reinstate Monica
CC BY-SA 4.0
2023-12-06T19:27:38.303Z
Because integer promotion silently transforms unsigned into signed: https://www.reddit.com/r/C_Programming/comments/10jc3hu/dont_carelessly_rely_on_fixedsize_unsigned/
André L F S Bacci
CC BY-SA 4.0
2023-12-06T19:49:04.277Z
That case concerns an `int` which is wider than the `uint32_t` the operands have (i.e., do not rely on a 4 byte `int` assumption). In that case, lesser-than-int-ranked integer operands are promoted to `int` or `unsigned int` as part of the *integer promotions* (n1570, 6.3.1.1). But here, [unsigned] `int` is used already, so there is no promotion. The operands of `unsigned int` and `int` types then undergo the *usual arithmetic conversions* to arrive at a *"common real type"*. In this case, the member is unsigned int and of equal rank to -4, so -4 is converted to unsigned int.
Peter - Reinstate Monica
<h3>Warning</h3>
<p>What is this warning about?</p>
<blockquote>
<pre><code>warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]
</code></pre>
</blockquote>
<p>This does not necessarily indicate an error, but it does indicate the potential for one. The way C implements mixed integers arithmetic -- ie, arithmetic between integers of different types -- involve promoting one or both integers so they both end up with a common type, then performing the arithmetic in that type. When mixing signedness, the results may be unexpected, and <em>unintended</em>, thus the heads up.</p>
<p>Due to how wrapping arithmetic works, however, it is in your case benign. For example, adding -3 (signed long) to an unsigned long will result in converting <code>-3</code> to an unsigned long (2<sup>64</sup>-3) and adding that, which will cause the result to be 3 less, after wrapping... exactly matching the expected result.</p>
<h3>Mixing</h3>
<p>You may, however, still want to revise how <em>your</em> language should work with regard to mixed arithmetic. Mixing integers of various signedness (though same magnitude) may catch users unaware.</p>
<p>With wrapping arithmetic, it kinda works, but once you move to big integers, you'll face troubles. Suddenly that conversion from <code>-3</code> to (2<sup>64</sup>-3) will lead to a big integer, not the current unsigned value minus 3.</p>
<p>I would strongly recommend just ditching unsigned integers for <em>calculus</em>. They may be useful, at lower bit widths, for <em>storage</em> purposes, in languages aiming to provide compact storage, but that is not your case. For you, all you get is that the maximum shifts from 2<sup>63</sup>-1 to 2<sup>64</sup>-1 and that's quite pointless in the grand scheme of things. Few values are ever greater than 2<sup>63</sup>-1 in practice, and of those that are, they are quite likely to be greater than 2<sup>64</sup>-1 too.</p>
<p>It's just not worth the trouble you'll cause your users.</p>
<h3>Yet</h3>
<p>If you <em>do</em> insist in having both signed and unsigned, my advise would be to store them <em>both</em> as unsigned.</p>
<p>As mentioned, with wrapping arithmetic you'll get the same result anyway, so storing as two different types is artificial complexity with no upside. And if you have to pick one, you're better of with unsigned: you won't need a non-standard <code>-fwrapv</code> flag then as unsigned arithmetic is wrapping by default in C.</p>
<p>The only time you need to use the signed representation -- for comparisons -- you can just cast prior to comparing in the comparison implementation. That's ensure that <code>-3 &lt; 0</code>, even if it's stored as 2<sup>64</sup>-3.</p>

CC BY-SA 4.0
2023-12-06T09:48:37.280Z
2023-12-06T09:48:37.280Z
Matthieu M.
<blockquote>
<p>I plan to implement overflow checks with transparent promotion to
arbitrary precision integers in the future.</p>
</blockquote>
<p>That's the key point driving my answer.</p>
<p>Right now, you only support a limited value range, covering -2<sup>63</sup> up to 2<sup>64</sup>-1, with the user having to choose between -2<sup>63</sup> up to 2<sup>63</sup>-1 or 0 up to 2<sup>64</sup>-1. If some calculation overflows, the user gets mathematically wrong results.</p>
<p>In the future, your language will transparently handle integers of arbitrary magnitude. Then, types like unsigned-32, or signed-64 might only make sense for storage purposes, when interacting with &quot;external&quot; libraries, but not for calculations, and will hopefully throw an exception when trying to store a non-compliant value.</p>
<p>So, for the current intermediate state I don't see much benefit in supporting both signed and unsigned integer types. You burden yourself with the questions you stated above, and the user with the decision which type to use, and the reasoning in whixh cases the result will be what he expects.</p>
<p>My recommendation is to get rid of the unsigned type now. Java shows that a language can do rather well with only signed integer types. It has a few peculiarities, but nothing serious.</p>
<p>If you're trying now to come up with a sound definition e.g. whether adding a signed and an unsigned value should give a signed or an unsigned result, you're simply wasting time better spent in implementing the seamless-integer semantics.</p>
<p>You'll inevitably face lots of unsolvable situations where limited-size arithemetic yields unexpected results, you already have a very good plan to solve this in the future, so go and follow this plan.</p>
<p>BTW, I used to program a lot in Common LISP, and I very much appreciated its notion of unlimited-size integers, only under the hood distinguishing between fixed and variable size.</p>

CC BY-SA 4.0
2023-12-06T13:17:01.990Z
2023-12-06T13:17:01.990Z
Ralf Kleberhoff
CC BY-SA 4.0
2023-12-06T17:16:13.197Z
I'm inclined to agree. I thought I needed unsigned because the language will interface with low level Linux structures, but after all these answers I'm thinking that's not the case at all. I should just make all arithmetic signed.
Matheus Moreira
<p>There seems to be three separate issues here:</p>
<ol>
<li>exposing separate signed and unsigned types in a programming language;</li>
<li>having signed and unsigned data storage in the implementation.</li>
<li>working around the quirks of C when writing an implementation in C.</li>
</ol>
<p>The second is easy: in general you want both, but in practice it's less cumbersome to use a single type (unsigned) for storage and to implement separate implementations of operators for those cases where results differ, especially <code>==</code>, <code>!=</code>, <code>&lt;</code>, <code>&lt;=</code>, <code>&gt;</code>, <code>&gt;=</code>, <code>&gt;&gt;</code>, <code>/</code> &amp; <code>%</code>.</p>
<blockquote>
<p>You only need implementations of <code>&lt;</code> and <code>==</code> as the rest can all be derived:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th style="text-align: center;">op</th>
<th style="text-align: center;">shorthand for</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align: center;"><code>a!=b</code></td>
<td style="text-align: center;"><code>not(a==b)</code></td>
</tr>
<tr>
<td style="text-align: center;"><code>a&lt;=b</code></td>
<td style="text-align: center;"><code>not(b&lt;a)</code></td>
</tr>
<tr>
<td style="text-align: center;"><code>a&gt;b</code></td>
<td style="text-align: center;"><code>b&lt;a</code></td>
</tr>
<tr>
<td style="text-align: center;"><code>a&gt;=b</code></td>
<td style="text-align: center;"><code>not(a&lt;b)</code></td>
</tr>
</tbody>
</table>
</div>
<p>Unlike C, you should have multiple implementations of <code>&lt;</code> and <code>==</code>:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>operator</th>
<th>operands</th>
<th>implementation</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>==</code></td>
<td>both same</td>
<td>naïve</td>
</tr>
<tr>
<td><code>==</code></td>
<td>mixed</td>
<td>false if not in common range</td>
</tr>
<tr>
<td><code>&lt;</code></td>
<td>both unsigned</td>
<td>naïve</td>
</tr>
<tr>
<td><code>&lt;</code></td>
<td>both signed</td>
<td>invert sign bits then as per unsigned</td>
</tr>
<tr>
<td><code>&lt;</code></td>
<td>signed+unsigned</td>
<td>true if first operand is negative or second operand exceeds max_signed</td>
</tr>
<tr>
<td><code>&lt;</code></td>
<td>unsigned+signed</td>
<td>false if first operand exceeds max_signed or second operand is negative</td>
</tr>
</tbody>
</table>
</div></blockquote>
<p>That also fixes the third issue: stick with just one, and be explicit about <em>every</em> type conversion. Write all your integer literals with an <code>S</code> or <code>U</code> suffix. Include guards to ensure assumptions actually hold, like: <code>assert(sizeof(uint32_t) &gt;= sizeof(int))</code></p>
<p>The first issue is less clear, since you've not said much about what's in your language.</p>
<p>Exposing &quot;native size&quot; signed and unsigned type is a known source of bugs, but that doesn't mean they're not useful.</p>
<p>I suggest that it would be less harmful to expose:</p>
<ol>
<li>Unbounded integers, which use whatever available implementation is available, or throw an exception (or just abort) when there's no available implementation. This would use BigInt when you get around to implementing it.</li>
<li>Modulus integers, where the programmer (in your language) specifies the lower and upper bounds, and assignments to such a variable are implicitly mod-whatever. You can abort at compile time if you don't support their choice of bounds. In principle you could allow any pair of bounds, but initially you'd only want to allow the pairs that correspond to 8-, 16-, 32-, or 64-bit ints, signed and unsigned.</li>
</ol>
<p>As for literals, I suggest copying what Go does: a numeric literal has its own notional type, but you can't declare a variable of this type. Instead, a literal is silently and implicitly converted to any numeric type (as long as it fits). If your language does type inference, then a numeric literal also has a preferred standard type. The compiler should perform all constant folding using &quot;infinite precision&quot; before using the results to generate code.</p>
<p>PS: having modulus apply on assignment means you actually need dual implementations of most arithmetic operators, one that traps on overflow, and one that ignores overflow (because it gets the right answer when later applying modulus). If you eventually get around implementing &quot;arbitrary modulus&quot;, the target modulus needs to be included as a hidden third parameter to the non-trapping operators.</p>

CC BY-SA 4.0
2023-12-09T04:33:07.800Z
2023-12-10T21:12:00.127Z
2023-12-10T21:12:00.127Z
Martin Kealey
<p>To prevent the warning, just use an explicit cast:</p>
<pre><code>/* accumulator.type == UINT &amp;&amp; argument.type == SINT */
accumulator.as.unsigned_integer += (unsigned long)argument.as.signed_integer;
</code></pre>
<p>This cast is well defined, and on a two's complement implementation it simply reinterprets the value as unsigned, there's no runtime overhead.</p>

CC BY-SA 4.0
2023-12-05T22:08:18.120Z
2023-12-05T22:08:18.120Z
Barmar
<p>Unsigned integers may cause difficult to find bugs if they overflow into negative side (that is much more likely to happen than four byte int overflowing from unsigned four byte int):</p>
<pre><code>  for (auto x = 0; x &lt; myvector.size(); x++) {
    if (x - 1 &lt; 1000) {
      // This code runs for x == 0 !
    }
  }
</code></pre>
<p>This generates no warning but does not work as expected. Subtracting 1 from 0 of the unsigned type (as inferred by <code>auto</code>) results a large number, more than 1000. Differently, using int would give as a warning about &quot;mixing signed and unsigned&quot; but it works.</p>
<p>In C++, many container and similar classes <a href="https://cplusplus.com/reference/vector/vector/size/" rel="nofollow noreferrer">return unsigned integers</a> without any real need. QT containers <a href="https://doc.qt.io/qt-5/qvector.html#size" rel="nofollow noreferrer">return sizes as signed integers</a>.</p>

CC BY-SA 4.0
2023-12-13T17:04:30.927Z
2023-12-13T17:04:30.927Z
Audrius Meškauskas
<p>The real quastion you need to ask (and answer) is &quot;what should happen if the result of the operation does not fit in the result type&quot; (what happens on underflow and overflow).  Related to this is &quot;what is the result type of an operation on a signed and an unsigned type&quot;.</p>
<p>In C when you do an operation on a signed and unsigned value (at least for types at least as large as <code>int</code>) it does it as unsigned (converting the signed value to unsigned for the operation).  That is largely because overflow of signed operations is undefined in C while overflow of unsigned is well-defined, so as long as you have unsigned types<sup>1</sup>, you don't fall into undefined behavior.</p>
<p>If you don't care what happens on overflow, you can just ignore the warning and get whatever you get.  If you do care, however, you need to decide what should happen first, and then you can write the code to get that result.  Maybe converting to some bigint representation?</p>
<hr />
<p><sup>1</sup><sub>Yes, for unsigned types smaller than an int, they'll first be converted to (signed) int, which is sometimes unfortunate and annoying (and ends up requiring extra explicit cases to make things work properly)</sub></p>

CC BY-SA 4.0
2023-12-12T01:53:49.387Z
2023-12-12T01:53:49.387Z
Chris Dodd
<p>You are getting a warning, not an error. The C or C++ standard tell exactly how mixing of signed and unsigned work, it is just that the rules are complicated and might not do what you expect or want, and therefore a warning is issued.</p>
<p>You need to decide what result exactly you want, and then you have to write the code to achieve these results. And if you add the exact conversions that the C rules would imply, then the warnings go away.</p>

CC BY-SA 4.0
2023-12-13T20:15:10.000Z
2023-12-13T20:15:10.000Z
gnasher729
<blockquote>
<p>So is there a correct way to implement this? Any pitfalls and footguns I should be considering? How do other languages do it?</p>
</blockquote>
<p>Your proposed struct value is utterly bizarre and no language I know of works that way.  Typically, a dynamically typed language will have just one integer type, and if it has a concept of a 'signed integer' or 'unsigned integer', that will be an <em>annotation</em>; you can check if a term satisfies the properties of an unsigned integer (being that it is an integer and it is non-negative), but it is still an integer, and if you add it to another integer, the result will also be an integer (the properties of which integer you can also check).</p>
<p>With that said, many languages include both integers and floating point numbers.  The relationship between integers and floating point numbers is similar to the relationship between (fixed-width) integers and natural numbers (aka 'signed' and 'unsigned'), in that they are both subsets of the rational numbers, but neither is a subset of the other (so neither can losslessly be converted to the other's format).  In that case, most languages make the result a floating-point number (it is a question whether it would be better to round once or twice, but I will ignore that for now).  Why?  Most 'common' integers (those with magnitude <span class="math-container">$\le 2^{53}$</span>, and many others besides) are floating-point numbers, whereas a great many 'common' floating-point numbers (like 0.5) are not integers, so taking the result to be a floating-point number is more likely to be useful.  You could similarly note that negative signed numbers with small magnitude are common, whereas unsigned numbers with very large magnitude are uncommon, so the result should be signed.  But this is still incredibly error-prone and happens to be a major footgun in c.</p>
<p>Another source of inspiration could be machine codes.  There, signed and unsigned integers are not distinguished at the data level—they are all just bitstrings—but rather by the operations we perform on them.  Addition is the same always, but we can have a signed comparison or an unsigned comparison.  You may also be interested in <a href="https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf" rel="nofollow noreferrer">this paper</a>.</p>

CC BY-SA 4.0
2023-12-05T20:45:12.733Z
2023-12-10T20:53:46.427Z
2023-12-10T20:53:46.427Z
Moonchild
CC BY-SA 4.0
2023-12-05T20:58:05.833Z
The structure seems bizarre but it's just a fat pointer structure. One word holds a descriptor, another holds the actual value which may be signed, unsigned, arbitrary pointer, or a pointer to a heap allocated language object. This lets me very easily work with primitives. I asked about it recently, [on stack exchange](https://softwareengineering.stackexchange.com/q/448875/9782) and [on reddit](https://old.reddit.com/r/ProgrammingLanguages/comments/186nai0/tagged_pointers_vs_fat_pointers/). I've grown to like it a lot and I'm almost done converting my entire interpreter to this approach.
Matheus Moreira
CC BY-SA 4.0
2023-12-05T21:00:25.083Z
Python *used* to have two dynamic integer types (`int` and `long`), but that was a matter of size, not signedness.  And the distinction was abolished in 3.0 anyway (making `long` the new `int`).
dan04
CC BY-SA 4.0
2023-12-05T22:06:58.817Z
What is bizarre is distinguishing signed and unsigned types in a dynamically typed language.  The discriminated union representation is completely standard.
Moonchild
CC BY-SA 4.0
2023-12-05T22:10:47.060Z
@Moonchild Maybe the intent is to avoid some of the weirdness that you get with bitwise operations in Python.
Barmar
CC BY-SA 4.0
2023-12-05T22:52:18.617Z
What is weird about bitwise operations in python?  I find them very simple and intuitive.
Moonchild
CC BY-SA 4.0
2023-12-06T16:37:20.140Z
Negative numbers act like they have an infinite number of leading 1's when doing bit shifting.
Barmar
CC BY-SA 4.0
2023-12-06T17:18:55.893Z
"There, signed and unsigned integers are not distinguished at the data level—they are all just bitstrings—but rather by the operations we perform on them" this is really wise. I like this approach.
Matheus Moreira
CC BY-SA 4.0
2023-12-06T19:46:57.347Z
@Barmar that is completely standard.
Moonchild
CC BY-SA 4.0
2023-12-06T20:20:46.010Z
I can't remember the specifics, but I know I've seen several [so] questions due to situations where Python bitwise operations produce unexpected (e.g. different from C) results due to Python's multi-precision integers.
Barmar
CC BY-SA 4.0
2023-12-07T16:52:23.703Z
You can get C-style *n*-bit `unsigned` operator semantics by ANDing the result with `(2**n - 1)`.
dan04
CC BY-SA 4.0
2023-12-07T21:15:09.843Z
Python's integers behave exactly the same as c's in the absence of overflow.  On overflow, python integers behave sensibly and c integers do not.  (Technically, right-shifting a signed integer is undefined behaviour in c, but the way it behaves in practice is the same as python.)
Moonchild
CC BY-SA 4.0
2023-12-11T21:05:54.353Z
@Moonchild: If one treats the behavior of integers as a generalization of the behavior of the bottom N bits of mathematical integers, there will only be one natural way for a signed right shift to work.  The value -16 would "mathematically" represented as an infinite number of ones followed by four zeroes.  Shifting that right one place would yield an infinite number of ones, followed by another one and then three zeroes.  The only reason for a two's-complement implementation to process a right-shift any other way would be for compatibility with code that predates the invention of 'unsigned'.
supercat
# Correctness of mixed signed/unsigned arithmetic
Posted by: username_0 on 2023-12-05
I'm implementing signed and unsigned integers in my language. They are represented in C as signed long and unsigned long respectively.
struct value {
    enum type type; / SINT, UINT, ... */

    union {
          signed long sint;
        unsigned long uint;
        /* more types... */
    } as;
};

Basic arithmetic operations such as + and - may operate on integers of mixed signedness depending on the types of the operands:
struct value accumulator, argument;
/* ... */

/* accumulator.type == UINT && argument.type == SINT */
accumulator.as.unsigned_integer += argument.as.signed_integer;

This code causes the C compiler to emit warnings like:
warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]

Which makes me worried about the correctness of this implementation.
I considered simply making it an error to operate on values of mixed signedness. I feel this would make the language too annoying to use though since the programmer would be required to defensively convert the integers every single time.
I currently handle overflows by letting the values wrap around. I assume two's complement integer representation and compile with -fwrapv. I plan to implement overflow checks with transparent promotion to arbitrary precision integers in the future. I want to make integers work seamlessly just like they do in Python and Ruby.
So is there a correct way to implement this? Any pitfalls and footguns I should be considering? How do other languages do it?
**Tags:** language-design implementation c math integers
> **Comments:**
> **username_1**: Welcome to PLDI! It might be useful to know how you handle overflow with signed+signed and unsigned+unsigned operations. Whether it's checked, wrapping, or UB might influence the decision for how to handle signed+unsigned  
> **username_0**: @RydwolfPrograms, it's currently wrapping as I assume two's complement integer representation and compile with `-fwrapv` but I plan to implement overflow checks with transparent promotion to arbitrary precision integers in the future, like in Python and Ruby.  
> **username_2**: I would introduce unsigned integers only as a special case of a general feature: User-defined integers with restricted value ranges, the way Ada does it (e.g. `Small_Int` on [this page](https://www.adaic.org/resources/add_content/standards/05rm/html/RM-3-2-2.html)).  
> **username_3**: You might like to consider having an unnamed union, so that you can then write `x.uint` rather than `x.as.uint`.  
> **username_0**: @MartinKealey I've always used unnamed unions but since discovering the `as` idiom I've come to prefer it. Short, correct, reads like natural english, distinguishes union fields from regular types and makes the type punning explicit.  
> **username_4**: The answer to “is there a correct way to implement this?” depends on your choice of integer model. I think a good baseline is [As-if Infinitely Ranged](https://www.researchgate.net/publication/221542289_As-If_Infinitely_Ranged_Integer_Model) (AIR): fixed-precision integer arithmetic is correct when it always either gives the same answer as arbitrary-precision arithmetic would have, or signals an error if that value isn’t representable.  
---
## 9 answers
### Answer by username_12 on 2023-12-05. Score: 5 | Accepted answer
> So is there a correct way to implement this? Any pitfalls and footguns I should be considering? How do other languages do it?

Your proposed struct value is utterly bizarre and no language I know of works that way. Typically, a dynamically typed language will have just one integer type, and if it has a concept of a 'signed integer' or 'unsigned integer', that will be an *annotation*; you can check if a term satisfies the properties of an unsigned integer (being that it is an integer and it is non-negative), but it is still an integer, and if you add it to another integer, the result will also be an integer (the properties of which integer you can also check).

With that said, many languages include both integers and floating point numbers. The relationship between integers and floating point numbers is similar to the relationship between (fixed-width) integers and natural numbers (aka 'signed' and 'unsigned'), in that they are both subsets of the rational numbers, but neither is a subset of the other (so neither can losslessly be converted to the other's format). In that case, most languages make the result a floating-point number (it is a question whether it would be better to round once or twice, but I will ignore that for now). Why? Most 'common' integers (those with magnitude $\le 2^{53}$, and many others besides) are floating-point numbers, whereas a great many 'common' floating-point numbers (like 0.5) are not integers, so taking the result to be a floating-point number is more likely to be useful. You could similarly note that negative signed numbers with small magnitude are common, whereas unsigned numbers with very large magnitude are uncommon, so the result should be signed. But this is still incredibly error-prone and happens to be a major footgun in c.

Another source of inspiration could be machine codes. There, signed and unsigned integers are not distinguished at the data level—they are all just bitstrings—but rather by the operations we perform on them. Addition is the same always, but we can have a signed comparison or an unsigned comparison. You may also be interested in [this paper](https://jorgenavas.github.io/papers/ACM-TOPLAS-wrapped.pdf).
> **Comments:**
> **username_0** (2023-12-05): The structure seems bizarre but it's just a fat pointer structure. One word holds a descriptor, another holds the actual value which may be signed, unsigned, arbitrary pointer, or a pointer to a heap allocated language object. This lets me very easily work with primitives. I asked about it recently, [on stack exchange](https://softwareengineering.stackexchange.com/q/448875/9782) and [on reddit](https://old.reddit.com/r/ProgrammingLanguages/comments/186nai0/tagged_pointers_vs_fat_pointers/). I've grown to like it a lot and I'm almost done converting my entire interpreter to this approach.  
> **username_13** (2023-12-05): Python *used* to have two dynamic integer types (`int` and `long`), but that was a matter of size, not signedness.  And the distinction was abolished in 3.0 anyway (making `long` the new `int`).  
> **username_12** (2023-12-05): What is bizarre is distinguishing signed and unsigned types in a dynamically typed language.  The discriminated union representation is completely standard.  
> **username_8** (2023-12-05): @Moonchild Maybe the intent is to avoid some of the weirdness that you get with bitwise operations in Python.  
> **username_12** (2023-12-05): What is weird about bitwise operations in python?  I find them very simple and intuitive.  
> **username_8** (2023-12-06): Negative numbers act like they have an infinite number of leading 1's when doing bit shifting.  
> **username_0** (2023-12-06): "There, signed and unsigned integers are not distinguished at the data level—they are all just bitstrings—but rather by the operations we perform on them" this is really wise. I like this approach.  
> **username_12** (2023-12-06): @Barmar that is completely standard.  
> **username_8** (2023-12-06): I can't remember the specifics, but I know I've seen several [so] questions due to situations where Python bitwise operations produce unexpected (e.g. different from C) results due to Python's multi-precision integers.  
> **username_13** (2023-12-07): You can get C-style *n*-bit `unsigned` operator semantics by ANDing the result with `(2**n - 1)`.  
> **username_12** (2023-12-07): Python's integers behave exactly the same as c's in the absence of overflow.  On overflow, python integers behave sensibly and c integers do not.  (Technically, right-shifting a signed integer is undefined behaviour in c, but the way it behaves in practice is the same as python.)  
> **username_14** (2023-12-11): @Moonchild: If one treats the behavior of integers as a generalization of the behavior of the bottom N bits of mathematical integers, there will only be one natural way for a signed right shift to work.  The value -16 would "mathematically" represented as an infinite number of ones followed by four zeroes.  Shifting that right one place would yield an infinite number of ones, followed by another one and then three zeroes.  The only reason for a two's-complement implementation to process a right-shift any other way would be for compatibility with code that predates the invention of 'unsigned'.  
---
### Answer by username_5 on 2023-12-05. Score: 5
This code causes the C compiler to emit warnings like: [...]
Which makes me worried about the correctness of this implementation.

Let's examine this with an example:
accumulator.as.unsigned_integer = 2;
argument.as.signed_integer      = -4;

accumulator.as.unsigned_integer += argument.as.signed_integer;

So then accumulator.as.unsigned_integer will:

have an small number, or;
be near to 0xffff...ffff, or;
will trap some math exception?

And, with another C compiler, or in another CPU, the reply above will remain?

This warning is telling you this code is not portable, because it contains behavior that is not guaranteed to hold (or even exist at all!) by C language standard (a.k.a., undefined behavior).
So yes, you should be worried that mixing signed with unsigned may produce weird results (as above) or produce different results (or no result at all) when compiling this code with another C compiler or in another CPU/architecture.
> **Comments:**
> **username_2** (2023-12-06): Why would it trap? Unsigned arithmetic in C is well-defined as modulo arithmetic. The result will be correct (if applicable, modulo 2^n) if interpreted as unsigned. It will, interestingly, also be "correct" if interpreted as signed; in the example, the result of the addition modulo 2^n, UINT_MAX-1, has the same bit representation as a signed -2 in 2's complement. In C it's also OK to convert the type through a union.  
> **username_5** (2023-12-06): Because integer promotion silently transforms unsigned into signed: https://www.reddit.com/r/C_Programming/comments/10jc3hu/dont_carelessly_rely_on_fixedsize_unsigned/  
> **username_2** (2023-12-06): That case concerns an `int` which is wider than the `uint32_t` the operands have (i.e., do not rely on a 4 byte `int` assumption). In that case, lesser-than-int-ranked integer operands are promoted to `int` or `unsigned int` as part of the *integer promotions* (n1570, 6.3.1.1). But here, [unsigned] `int` is used already, so there is no promotion. The operands of `unsigned int` and `int` types then undergo the *usual arithmetic conversions* to arrive at a *"common real type"*. In this case, the member is unsigned int and of equal rank to -4, so -4 is converted to unsigned int.  
---
### Answer by username_6 on 2023-12-06. Score: 3
Warning
What is this warning about?

warning: implicit conversion changes signedness: 'long' to 'unsigned long' [-Wsign-conversion]


This does not necessarily indicate an error, but it does indicate the potential for one. The way C implements mixed integers arithmetic -- ie, arithmetic between integers of different types -- involve promoting one or both integers so they both end up with a common type, then performing the arithmetic in that type. When mixing signedness, the results may be unexpected, and unintended, thus the heads up.
Due to how wrapping arithmetic works, however, it is in your case benign. For example, adding -3 (signed long) to an unsigned long will result in converting -3 to an unsigned long (264-3) and adding that, which will cause the result to be 3 less, after wrapping... exactly matching the expected result.
Mixing
You may, however, still want to revise how your language should work with regard to mixed arithmetic. Mixing integers of various signedness (though same magnitude) may catch users unaware.
With wrapping arithmetic, it kinda works, but once you move to big integers, you'll face troubles. Suddenly that conversion from -3 to (264-3) will lead to a big integer, not the current unsigned value minus 3.
I would strongly recommend just ditching unsigned integers for calculus. They may be useful, at lower bit widths, for storage purposes, in languages aiming to provide compact storage, but that is not your case. For you, all you get is that the maximum shifts from 263-1 to 264-1 and that's quite pointless in the grand scheme of things. Few values are ever greater than 263-1 in practice, and of those that are, they are quite likely to be greater than 264-1 too.
It's just not worth the trouble you'll cause your users.
Yet
If you do insist in having both signed and unsigned, my advise would be to store them both as unsigned.
As mentioned, with wrapping arithmetic you'll get the same result anyway, so storing as two different types is artificial complexity with no upside. And if you have to pick one, you're better of with unsigned: you won't need a non-standard -fwrapv flag then as unsigned arithmetic is wrapping by default in C.
The only time you need to use the signed representation -- for comparisons -- you can just cast prior to comparing in the comparison implementation. That's ensure that -3 < 0, even if it's stored as 264-3.
---
### Answer by username_7 on 2023-12-06. Score: 3
> I plan to implement overflow checks with transparent promotion to
> arbitrary precision integers in the future.

That's the key point driving my answer.

Right now, you only support a limited value range, covering -263 up to 264-1, with the user having to choose between -263 up to 263-1 or 0 up to 264-1. If some calculation overflows, the user gets mathematically wrong results.

In the future, your language will transparently handle integers of arbitrary magnitude. Then, types like unsigned-32, or signed-64 might only make sense for storage purposes, when interacting with "external" libraries, but not for calculations, and will hopefully throw an exception when trying to store a non-compliant value.

So, for the current intermediate state I don't see much benefit in supporting both signed and unsigned integer types. You burden yourself with the questions you stated above, and the user with the decision which type to use, and the reasoning in whixh cases the result will be what he expects.

My recommendation is to get rid of the unsigned type now. Java shows that a language can do rather well with only signed integer types. It has a few peculiarities, but nothing serious.

If you're trying now to come up with a sound definition e.g. whether adding a signed and an unsigned value should give a signed or an unsigned result, you're simply wasting time better spent in implementing the seamless-integer semantics.

You'll inevitably face lots of unsolvable situations where limited-size arithemetic yields unexpected results, you already have a very good plan to solve this in the future, so go and follow this plan.

BTW, I used to program a lot in Common LISP, and I very much appreciated its notion of unlimited-size integers, only under the hood distinguishing between fixed and variable size.
> **Comments:**
> **username_0** (2023-12-06): I'm inclined to agree. I thought I needed unsigned because the language will interface with low level Linux structures, but after all these answers I'm thinking that's not the case at all. I should just make all arithmetic signed.  
---
### Answer by username_3 on 2023-12-09. Score: 1
There seems to be three separate issues here:

1. exposing separate signed and unsigned types in a programming language;
2. having signed and unsigned data storage in the implementation.
3. working around the quirks of C when writing an implementation in C.

The second is easy: in general you want both, but in practice it's less cumbersome to use a single type (unsigned) for storage and to implement separate implementations of operators for those cases where results differ, especially `==`, `!=`, `<`, `<=`, `>`, `>=`, `>>`, `/` & `%`.

> You only need implementations of `<` and `==` as the rest can all be derived:
>
> | op | shorthand for |
> | --- | --- |
> | `a!=b` | `not(a==b)` |
> | `a<=b` | `not(b` |
> | `a>b` | `b` |
> | `a>=b` | `not(a` |
>
> Unlike C, you should have multiple implementations of `<` and `==`:
>
> | operator | operands | implementation |
> | --- | --- | --- |
> | `==` | both same | naïve |
> | `==` | mixed | false if not in common range |
> | `<` | both unsigned | naïve |
> | `<` | both signed | invert sign bits then as per unsigned |
> | `<` | signed+unsigned | true if first operand is negative or second operand exceeds max\_signed |
> | `<` | unsigned+signed | false if first operand exceeds max\_signed or second operand is negative |

That also fixes the third issue: stick with just one, and be explicit about *every* type conversion. Write all your integer literals with an `S` or `U` suffix. Include guards to ensure assumptions actually hold, like: `assert(sizeof(uint32_t) >= sizeof(int))`

The first issue is less clear, since you've not said much about what's in your language.

Exposing "native size" signed and unsigned type is a known source of bugs, but that doesn't mean they're not useful.

I suggest that it would be less harmful to expose:

1. Unbounded integers, which use whatever available implementation is available, or throw an exception (or just abort) when there's no available implementation. This would use BigInt when you get around to implementing it.
2. Modulus integers, where the programmer (in your language) specifies the lower and upper bounds, and assignments to such a variable are implicitly mod-whatever. You can abort at compile time if you don't support their choice of bounds. In principle you could allow any pair of bounds, but initially you'd only want to allow the pairs that correspond to 8-, 16-, 32-, or 64-bit ints, signed and unsigned.

As for literals, I suggest copying what Go does: a numeric literal has its own notional type, but you can't declare a variable of this type. Instead, a literal is silently and implicitly converted to any numeric type (as long as it fits). If your language does type inference, then a numeric literal also has a preferred standard type. The compiler should perform all constant folding using "infinite precision" before using the results to generate code.

PS: having modulus apply on assignment means you actually need dual implementations of most arithmetic operators, one that traps on overflow, and one that ignores overflow (because it gets the right answer when later applying modulus). If you eventually get around implementing "arbitrary modulus", the target modulus needs to be included as a hidden third parameter to the non-trapping operators.
---
### Answer by username_8 on 2023-12-05. Score: 0
To prevent the warning, just use an explicit cast:
/* accumulator.type == UINT && argument.type == SINT */
accumulator.as.unsigned_integer += (unsigned long)argument.as.signed_integer;

This cast is well defined, and on a two's complement implementation it simply reinterprets the value as unsigned, there's no runtime overhead.
---
### Answer by username_9 on 2023-12-13. Score: 0
Unsigned integers may cause difficult to find bugs if they overflow into negative side (that is much more likely to happen than four byte int overflowing from unsigned four byte int):
  for (auto x = 0; x < myvector.size(); x++) {
    if (x - 1 < 1000) {
      // This code runs for x == 0 !
    }
  }

This generates no warning but does not work as expected. Subtracting 1 from 0 of the unsigned type (as inferred by auto) results a large number, more than 1000. Differently, using int would give as a warning about "mixing signed and unsigned" but it works.
In C++, many container and similar classes return unsigned integers without any real need. QT containers return sizes as signed integers.
---
### Answer by username_10 on 2023-12-12. Score: 0
The real quastion you need to ask (and answer) is "what should happen if the result of the operation does not fit in the result type" (what happens on underflow and overflow). Related to this is "what is the result type of an operation on a signed and an unsigned type".

In C when you do an operation on a signed and unsigned value (at least for types at least as large as `int`) it does it as unsigned (converting the signed value to unsigned for the operation). That is largely because overflow of signed operations is undefined in C while overflow of unsigned is well-defined, so as long as you have unsigned types1, you don't fall into undefined behavior.

If you don't care what happens on overflow, you can just ignore the warning and get whatever you get. If you do care, however, you need to decide what should happen first, and then you can write the code to get that result. Maybe converting to some bigint representation?

---

1Yes, for unsigned types smaller than an int, they'll first be converted to (signed) int, which is sometimes unfortunate and annoying (and ends up requiring extra explicit cases to make things work properly)
---
### Answer by username_11 on 2023-12-13. Score: -1
You are getting a warning, not an error. The C or C++ standard tell exactly how mixing of signed and unsigned work, it is just that the rules are complicated and might not do what you expect or want, and therefore a warning is issued.

You need to decide what result exactly you want, and then you have to write the code to achieve these results. And if you add the exact conversions that the C rules would imply, then the warnings go away.
---
