Is there a formula for overflow?
Nov 30
Basile B.
Nov 30
Basile B.

I am reading through Ali's book about D, and he gives the following examples for an overflow:

``````import std.stdio;
void main() {
// 3 billion each
uint number_1 = 3000000000;
uint number_2 = 3000000000;
}
writeln("maximum value of uint: ", uint.max);
writeln("
number_1: ", number_1);
writeln("
number_2: ", number_2);
writeln("
sum: ", number_1 + number_2);
writeln("OVERFLOW! The result is not 6 billion!");
``````

The result overflows and is 1705032704.

Also for the second example, it overflows and comes up with the value of 4294967286:

``````void main() {
uint number_1 = 10;
uint number_2 = 20;
writeln("PROBLEM! uint cannot have negative values:");
writeln(number_1 - number_2);
writeln(number_2 - number_1);
}
``````

Also a fun one, the following produces 4294967295:

``````uint number = 1;
writeln("negation: ", -number);
``````

But the book doesn't talk about why the D compiler came up with these results (and it also goes for division/multiplication) for the overflow (or maybe it did further down ?), as in it didn't talk about the formula it used for calculating this value.

I am curious as to what formula the D compiler uses for calculating 'overflowed' values, if such thing exists? :)

Regards,
thebluepandabear

On Wednesday, 30 November 2022 at 03:07:44 UTC, thebluepandabear wrote:

>

I am reading through Ali's book about D, and he gives the following examples for an overflow:

``````import std.stdio;
void main() {
// 3 billion each
uint number_1 = 3000000000;
uint number_2 = 3000000000;
}
writeln("maximum value of uint: ", uint.max);
writeln("
number_1: ", number_1);
writeln("
number_2: ", number_2);
writeln("
sum: ", number_1 + number_2);
writeln("OVERFLOW! The result is not 6 billion!");
``````

writeln((3000000000LU + 3000000000LU) % uint.max);

>

The result overflows and is 1705032704.

Also for the second example, it overflows and comes up with the value of 4294967286:

``````void main() {
uint number_1 = 10;
uint number_2 = 20;
writeln("PROBLEM! uint cannot have negative values:");
writeln(number_1 - number_2);
writeln(number_2 - number_1);
}
``````

Also a fun one, the following produces 4294967295:

``````uint number = 1;
writeln("negation: ", -number);
``````

writeln( cast(uint) -(cast(int)1) );

>

But the book doesn't talk about why the D compiler came up with these results (and it also goes for division/multiplication) for the overflow (or maybe it did further down ?), as in it didn't talk about the formula it used for calculating this value.

I am curious as to what formula the D compiler uses for calculating 'overflowed' values, if such thing exists? :)

Regards,
thebluepandabear

It's always a wraparound (think modulo) but your examples with negative number can be explained because there are hidden unsigned to signed implicit convertions.
That the only special things D does.

On Wednesday, 30 November 2022 at 03:19:49 UTC, Basile B. wrote:

>

[...]
It's always a wraparound (think modulo) but your examples with negative number can be explained because there are hidden unsigned to signed implicit convertions.
That the only special things D does.

forgot to say, you can use the dmd flag -vcg-ast to see the hidden rewrites

On Wednesday, 30 November 2022 at 03:19:49 UTC, Basile B. wrote:

>

writeln((3000000000LU + 3000000000LU) % uint.max);

It's actually

``````writeln((3000000000LU + 3000000000LU) % (uint.max.to!ulong + 1));
``````

or

``````writeln((3000000000LU + 3000000000LU) & uint.max);
``````

On Wednesday, 30 November 2022 at 03:07:44 UTC, thebluepandabear wrote:

>

I am curious as to what formula the D compiler uses for calculating 'overflowed' values, if such thing exists? :)

Regards,
thebluepandabear

1. If one of the values is real, then the other value is converted to real
2. Else, if one of the values is double, then the other value is converted to double
3. Else, if one of the values is float, then the other value is converted to float
4. Else, first integer promotions are applied according to the table above, and then the following rules are followed:
A. If both types are the same, then no more steps needed
B. If both types are signed or both types are unsigned, then the narrower value is converted to the wider type
C. If the signed type is wider than the unsigned type, then the unsigned value is converted to the signed type
D. Otherwise the signed type is converted to the unsigned type

SDB@79

>

then the narrower value is converted to the wider type
C. If the signed type is wider than the unsigned type, then the unsigned value is converted to the signed type
D. Otherwise the signed type is converted to the unsigned type

SDB@79

```On 11/29/22 19:07, thebluepandabear wrote:

> But the book doesn't talk about why the D compiler came up with these
> results

The compiler doesn't do anything special. It's all about the lack of bits to store the value. If the result needs 33 bits but the type has only 32 bits, the contribution of the highest bit is simply lost.

Ali

```

On Wednesday, 30 November 2022 at 11:40:36 UTC, thebluepandabear wrote:

> >

then the narrower value is converted to the wider type
C. If the signed type is wider than the unsigned type, then the unsigned value is converted to the signed type
D. Otherwise the signed type is converted to the unsigned type

SDB@79

You cannot fully grasp the topics without fully knowing the above items.

SDB@79

```On Wed, Nov 30, 2022 at 03:07:44AM +0000, thebluepandabear via Digitalmars-d-learn wrote:
> I am reading through Ali's book about D, and he gives the following examples for an overflow:
[...]
> The result overflows and is 1705032704.
>
> Also for the second example, it overflows and comes up with the value of 4294967286:
[...]
> Also a fun one, the following produces 4294967295:
[...]
> But the book doesn't talk about why the D compiler came up with these results (and it also goes for division/multiplication) for the overflow (or maybe it did further down ?), as in it didn't talk about the formula it used for calculating this value.
>
> I am curious as to what formula the D compiler uses for calculating 'overflowed' values, if such thing exists? :)
[...]

First, you have to understand that it's not the D compiler that imposes some arbitrary maximum after which an integer value will overflow. To overflow rules are more-or-less a description of how the hardware behaves under the hood, rather than something the compiler deliberately imposes.

The value 4294967296 is actually 2^32. Why 2^32? Because that's the number of distinct values a 32-bit machine register can hold. In fact, the maximum value that a 32-bit register can hold is (2^32 - 1), i.e., 4294967295, because 0 is one of the values represented.  Now, (2^32 - 1) is the maximum for uint, but for int, one bit is reserved for indicating the sign of the value, so the actual maximum is (2^31 - 1), i.e., 2147483647, which, incidentally, is the value of int.max.

As for the actual overflow behaviour, it's a simple consequence of the
2's complement representation of integers. I.e., -1 is represented not
as:
0b1000_0000_0000_0000__0000_0000_0000_0001

but rather as:

0b1111_1111_1111_1111__1111_1111_1111_1111 (i.e. 0xFFFF_FFFF)

The most negative value that can be represented in 32-bit 2's complement is:

0b1000_0000_0000_0000__0000_0000_0000_0000 (0x8000_0000)

which is -2^31 == -2147483648, which, incidentally, is int.min.

Why 2's complement?  Well, because that's what the machine implements... but why did the engineers choose to implement it that way?  Because 2's complement representation has the interesting property that addition and subtraction can be done exactly as if the values were unsigned, and you'd get the correct results back when you reinterpret them as 2's complement.  I.e., if you add 1 to 0xFFFF_FFFF, interpreted as an unsigned integer, you get 0x0000_0000 (there's a leading 1 on the far left but it's in the 33rd bit, which doesn't fit in the machine register, so it gets discarded).  If you reinterpret 0xFFFF_FFFF in 2's complement as -1, then you have the nice result that (-1) + 1 == 0 (the + here is unsigned addition).

One consequence of this is that negation is implemented as:

-x == ~(x-1)

As a consequence of the 2's-complement representation of integers, and the way arithmetic operations are implemented, the overflow rules that you read about just fall out of the rules as natural consequences:

0x7FFF_FFFF + 1 == 0x8000_0000

i.e., interpreted as 2's complement:

2147483647 + 1 == -2147483648

Negating an unsigned number is equivalent to doing ~(x-1), so:

cast(uint) -1 == 0xFFFF_FFFF == 2^32 - 1 == 4294967295

0xB2D05E00) gives you:

0xB2D05E00 + 0xB2D05E00 == 1_65A0BC00

But that leading 1 is in the 33rd bit, which doesn't fit into a 32-bit register (i.e., it overflows). If you discard it, you get 0x65A0BC00, which in decimal is 1705032704.

So you see, none of this is D's own idiosyncratic rules; it's merely a reflection of how the machine implements 32-bit integer values. (Analogous results can be said for 64-bit values.)

T

--
If you want to solve a problem, you need to address its root cause, not just its symptoms. Otherwise it's like treating cancer with Tylenol...
```