Reinventing The Wheel

What is the 2's Complement?

The 2's complement is a mathematical operation on binary numbers, and is how most digital systems store numbers.
NB. Before reading any further, you should have a good understanding of the binary number system.

How To Take the 2's Complement

Method One

To take the 2's complement of a number, simply complement each bit, and then add one.


Example

The number 6 in binary is 0110, to take the 2's complement, complement each bit: 1001, and add 1: 1010

Method Two

Another way to take the 2's complement, is to begin with the bit on the right hand side, and move towards the left until you find the first 1, then complement each bit after that.


Example

The number ten in binary is 01010, the bit on the right hand side is 0, so we leave that, the next bit is 1, so each bit after that going towards the left we complement.
So we have 10110.

2's Complement and Negative Number Representation

If you take the 2's complement of a positive number, you get the negative representation of that number, and vice versa.
Example

If you take the 2's complement of 5 (0101), you get 1011 which is how you represent -5.
If you take the 2's complement of -5 (1011), you get 0101, which is 5.

How do you know if 1011 is -5, or 11?
Negative numbers are stored using 2’s complement combined with what is called “signed number representation”.
With signed number representation, the most significant bit (MSB), i.e. the number on the left, is used to represent whether the number is positive (0) or negative (1). This bit is known as the "sign bit".
You can use any number of bits to represent +ve or –ve numbers, as long as you follow the 2’s complement method, and remember that the MSB is the sign bit.

Example

The number 6 can be represented as 0110, so the –ve representation is 1010.
We can place any number of 0’s in front of 0110, so how would you represent 6 if you used 00110? Just follow the 2’s complement:
00110 -> 11010

We can see that any number of bits can be used, as long as you remember that the MSB represents the sign bit.

Example

To represent 6 in signed number representation, you can’t write 110. Since the MSB is 1, this number actually represents -2.

So what numbers can we represent with n bits?

Let’s start with an example.

Example

Not caring about 2’s complement or signed number representation, what combinations can you have with n = 4 bits?
With n = 4, you can have 24 = 16 combinations, as shown in the table below:
Binary Number Unsigned Value Signed Value
0000 0 0
0001 1 1
0010 2 2
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 8 -8
1001 9 -7
1010 10 -6
1011 11 -5
1100 12 -4
1101 13 -3
1110 14 -2
1111 15 -1

What about the 2’s complement of 1000 ?

Interestingly, if you take the 2’s complement of 1000, you get 1000!
Remember 1000 is -8, and not +8, since the MSB is 1.
It's not -0 either, since 0 and -0 are equal, and 0 is already represented by 0000. There is no need to have two representations for the one number.
To represent +8, you would need an extra bit (01000).
This confuses a lot of people, however if you just stick to the
rule for taking the 2's complement, you will see that 1000 it is equal to -8.

Formula

With 4 bits, you can have the numbers 0 to 15 (NB. 15 = 24-1), this provides us with 16 (or 24) numbers in total. Using unsigned number representation or you can have -8 (or -24) to +7 (or 24-1) (16 numbers in total) using signed number representation.
This provides us with the following formula:
With n bits, we can represent signed numbers –2n to 2n-1,
With n bits, we can represent unsigned numbers 0 to 2n-1.

Integer overflows in C#

If you have another look at the table above, notice how as you keep adding one, the numbers get higher until you reach 7. From 7, if you add one, you get an "over flow" and you go to the most negaitve number.
This is what happens in C# when you add one to an int (or some other data type) that is already the largest number it can be, and when this happens, a System.OverflowException is thrown.
Now you have an understanding of how integers work behind the scenes, you can now understand why, when adding 1, an int goes from 2147483647 (or 232-1) to -2147483648 (-232) (Remember the formula?).

Why does Int32.MaxValue = 2,147,483,647 ?

Many programmers know that the maximum value an int can store is 2,147,483,647, but very few actually know why.
Now you know about 2’s complement and signed number representation, you can understand why Int32.MaxValue = 2,147,483,647!
As the name of the struct suggests, Int32 integers are stored using 32 bits. The first bit (or the MSB), is the sign bit, and the next 31 bits represent the number.
With this in mind, have a look at how 2,147,483,647 is stored in memory using binary:
0111 1111 1111 1111 1111 1111 1111 1111 (or 0x7FFFFFFF in Hex)
The spacing between each nibble (4 bits) is there for readability only.
As you can see this is the maximum number you can store using 32 bit signed number representation.
If you tried to increase this number by 1, you would get a carry into the MSB, which would set the sign bit to 1, and all the other bits to 0, this number would then be -2,147,483,648.
For more information have a look at MSDN.