Delving too deeply

What happens if you try to negate the smallest 32 bit integer in c#?

void Start()
{
    print(-int.MinValue);
}

If you try to compile this code, the compiler will helpfully emit error code CS0220: the operation overflows.

However, if you wrap it in a function:

int Negate(int value)
{
    return -value;
}

void Start()
{
    print(Negate(int.MinValue));
}

It compiles without errors.

But what does it do?

The value of int.MinValue is -2,147,483,648. So, you might expect it would return 2,147,483,648.

But, int.MaxValue is 2,147,483,647. That is one less than the value it would need. Accounting for that, you might think it would either throw an exception, or return 2,147,483,647.

In fact it returns -2,147,483,648.

The same behaviour happens with smaller integer representations like short and sbyte, returning -32,768 and -128 respectively.

To see why this is the case, it’s helpful to know how numbers are stored. For example, an 8 bit byte value has (as it’s name suggests) 8 bits, each of which can be either 0 or 1.

To work out how many combinations this gives us, start with 1 bit. With 1 bit we have two possible combinations: the bit is either 0 or 1. Each bit we add, doubles the combinations, since we have all the combinations we had before with the new bit set to 0, and again with the new bit as 1. Do that 8 times and we end up with 256 possible combinations in 8 bits.

\begin{align*}
\square &= \text{2 combinations} \\
\square\square &= \text{4 combinations} \\
\square\square\square &= \text{8 combinations} \\
\square\square\square\square &= \text{16 combinations} \\
\square\square\square\square\square &= \text{32 combinations} \\
\square\square\square\square\square\square &= \text{64 combinations} \\
\square\square\square\square\square\square\square &= \text{128 combinations} \\
\square\square\square\square\square\square\square\square &= \text{256 combinations} \\
\end{align*}

If you keep going, you will reach 65,536 for 16 bits, and 4,294,967,296 for 32 bits.

Now, if we need to represent both positive and negative numbers, we need to divide up those combinations somehow. So we take half of the combinations for the positive numbers and half for the negative.

However, that does leave an odd one out. What do we do with zero? Zero is not strictly positive or negative. But we have to assign it one way or another. And it seems only logical that the combination for zero ought to be all zeros.

\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0} = 0

And if we follow the convention for our normal number system, then positive one should be all zeros followed by a one on the right.

\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1} = 1

This gives us the desirable property, that we can add these numbers just by adding the bits. This works fine for 0 and 1, but what happens when we want to add 1 and 1? In that case, we follow the same rules as we do for normal numbers and carry 1 to the left. And so we can keep assigning numbers until we run out of bits.

\begin{align*}
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0} &= 0 \\
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1} &= 1 \\
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{0} &= 2 \\
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{1} &= 3 \\
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{0} &= 4 \\
... \\
\fbox{0}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0} &= 126 \\
\fbox{0}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1} &= 127 \\

\end{align*}

But when we reach 127 we have already used half of our combinations and we still need to represent the negatives.

One thing you might notice at this point, is that all of our positive numbers so far have a 0 in the leftmost bit. We can use this to quickly check that our number is positive. (Or at least zero.)

So for the negative numbers, the leftmost bit should be 1. And again it would be nice if in our representation when we add 1, it should give us the next number up. To start, we would need a representation for -1 such that adding 1 to it would naturally give us the representation for 0.

\begin{align*}
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1} \\
+ \fbox{1}\fbox{?}\fbox{?}\fbox{?}\fbox{?}\fbox{?}\fbox{?}\fbox{?} \\
=\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0} \\
\end{align*}

If we start at the right hand side, the first bit can’t be a zero, since that would leave a 1 in the result. So it must be a 1. But that would mean carrying 1 to the next position. So that bit would also need to be a 1 or it would put a 1 in the result. This continues all the way to the right until we carry 1 but we don’t have anywhere to put it. They all rolled over and one fell out, leaving us with all zeros.

they all rolled over and one fell out

— traditional nursery rhyme

With -1 defined, we can proceed as before, subtracting one each time until we run out of combinations:

\begin{align*}
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1} &= -1 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0} &= -2 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0}\fbox{1} &= -3 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0}\fbox{0} &= -4 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0}\fbox{1}\fbox{1} &= -5 \\
... \\
\fbox{1}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1} &= -127 \\
\fbox{1}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0} &= -128 \\
\end{align*}

Now we have assigned all of the combinations in an order that allows us to use our common arithmetic rules. We end up with 1 more negative number than positive numbers because we needed to represent zero somewhere.

But what happens now if we subtract 1 from -128, or add 1 to 127?

If we add 1 to 127, we end up with a bit overflowing into the negative bit. The negative bit changes from 0 to 1 and the result becomes -128.

If we subtract 1 from -128, the opposite happens: the 1 is borrowed out of the negative bit, turning it into positive 127.

Now we know all this, can we see why negating -128 would cause it to remain -128?

If we pair up the positive and negative number representations, we can see that there is a certain symmetry there:

\begin{align*}
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0} &= 0 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1} &= -1 \\
\\
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1} &= 1 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0} &= -2 \\
\\
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{0} &= 2 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0}\fbox{1} &= -3 \\
\\
\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{0}\fbox{1}\fbox{1} &= 3 \\
\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{1}\fbox{0}\fbox{0} &= -4 \\
\end{align*}

It seems that for every negative number, the opposite representation in terms of its bits is the positive equivalent minus 1. And this pattern continues for every negative number. So to negate any number in our representation, all we need to do is flip all the bits and then add 1.

And it works for all the numbers in the representation. The problem is, with the number -128, it returns 127 + 1. And, as we saw above, 127 + 1 wraps back around to -128. So we end up back where we started.

And the same thing happens with the 16 bit and 32 bit numbers.

So be aware of that when negating at the negative limit of your number representation.