Two’s complement and negative numbers for integers

In most if not all programming languages, you can have positive and negative integer numbers. These values never have a fractional part meaning that they do not have decimals. They are also usually called signed integers, because they have a representing bit in memory which tells if they are below or above and equal to zero, meaning(-) or (+).

When numbers don’t ever need to have a negative value, there is a representation called unsigned integer. This representation takes all of the space that negative values could have taken in memory, and adds them to positive values.

In C language their declarations go as follow:

/* Signed Integer */
int n = -2;
/* Unsigned Integer */
unsigned int m = 2;

This can also have a slight variation with a modifier called short or long, which basically allows the variables to store even greater data. The next table shows the value range and storage size of these kind of variables in C language.

Binary Representation

Numerical values stored in memory are represented as bits (0 or 1) in groups of bytes (8 bits).

A number such as 2 is saved in memory as

00000000 00000000 00000000 00000010

Which stands for 4 bytes of memory for a signed integer.

But what about negative numbers?, How does C language understand that a number has a negative value or not?

Here is where two´s complement of a binary is used. A complement is a transformation of the binary representation of a number that allows to have a depiction of negative values, for understanding Two’s complement, we must first see One’s Complement.

One’s Complement or 1’s Complement

It is a method used to represent negative binary numbers in signed type variables. In one’s complement, positive numbers (also known as non-complements) remain unchanged.

Negative numbers on the other hand, are represented by inverting the binary representation of a positive number. Since positive numbers always start with a “0”, the complement will always start with a “1” to indicate a negative number.

Example:

If we wanted to represented -1 we would need to take the inversion of 0. For this, we can use the bitwise operator ~ (one´s complement), which inverts all bits of a variable.

In C language, using printf, we would get:

#include <stdio.h>
int main()
{
/* Binary of 0: 00000000 */
    printf("Value 0: %d\n", 0); 
/* Binary of ~0: 11111111 */
    printf("Value ~0: %d\n", ~0);
/* Binary of 1: 00000001 */
    printf("Value 1: %d\n", 1);
/* Binary of ~1: 11111110 */
    printf("Value ~1%d\n", ~1);
/* Binary of 2: 00000010*/
    printf("Value 2: %d\n", 2);
/* Binary of ~2: 11111101*/
    printf("Value ~2: %d\n", ~2);
    return 0;
}
Value 0: 0
Value ~0: -1
Value 1: 1
Value ~1: -2
Value 2: 2
Value ~2: -3

An issue with this representation is that 0 has both a positive and negative value -0 and +0.

Two’s Complement or 2’s Complement

This is another method like the One’s complement to represent negative binary numbers when there is a signed type variable. In two’s complement, positive numbers remain unchanged from their base binary representation. A negative number, however, is represented by a binary number, which when added to its corresponding positive equivalent results in zero. In basic terms, two’s complement of a number is its one’s complement + 1.

The main advantage of two’s complement over one’s complement is that it is easier to generate the two’s complement of a signed binary number. Therefore, arithmetic operations are easier to perform when the numbers are represented this way. Besides this, 0 has a unique positive (+) representation.

If for example we have number 5, then its binary representation would be:

00101
Obtaining the One´s complement would result in
01010
And adding 1 (00001) would result in 
01011
Positive 5 Would have a first bit in 0 and Negative 5 would have this bit in 1 
01011 (+5)
11011 (-5)

This would be visualized as follows:

MSB is always 1 in case of negative numbers and 0 in case of positive numbers.

Range of Numbers:

Values represented this way in an n bits memory register can have a positive number as large as

{[2 ^ (n-1)] - 1}

, and a negative number as low as

-[2^(n-1)].

Arithmetic with 2’s Complement:

One of the advantages of representing signed values with 2’s complement is the possibility of performing binary arithmetic the easily on signed or unsigned numbers. It yields correct 2’s complement in result.

Addition:

We can simply convert the numbers we desire to operate on into 2’s complement and then perform a simple base 2 addition.

          0000 1000
        + 1111 1101
         ----------
Carry 1 <-0000 0101 = (+5)

As carry is 1 then the number is positive (signed bit).

Here, the carry is 1 but it goes out of bounds in the byte, hence it is not considered in the answer and the result is one byte long positive number.

Subtraction:

Similar to addition but here the subtrahend is first converted to its negative form and then it is added with minuend.

Example:

          0000 1000
        - 1111 0111
         ----------
Carry 0<-1111 1111 = (-1)

As carry is 0 then the number is negative (signed bit).

Multiplication:

This follows the same rules as a basic binary multiplication.

Example:

          1111 1100 (+4)
        * 0000 0100 (-4)
         ----------
Carry 0<-1111 0000=(-16)

As carry is 0 then the number is negative (signed bit).

Division:

For division, this consists of repeating two´s complement subtraction repeatedly.

• First calculate the 2’s complement of the divisor and then this converted divisor is to be added to the dividend.
• Now comes the next subtraction cycle. Here quotient replaces the dividend.
• This is repeated again and again up until the quotient is getting too small or zero. If it is not zero then it is treated as remainder.

Example:

          0000 0111 (+7)
        / 1111 1101 (-3)
          ----------
          0000 0100 = (+4)
          0000 0100 (+4)
        / 1111 1101 (-3)
          ----------
          0000 0100 = (+1) Remainder

Signed bit is 0 so the remainder is positive.

Overflow:

Signed values in programming languages have an issue regarding its size

When a signed value goes over its positive limit, it will start showing negative numbers from the lowest possible in memory and then increasing. This happens inversely with negative values. When a signed integer goes below the lowest number possible in memory, it will start showing positive values, starting from the highest positive number possible and then decreasing.

If for example we have limits of -10 and 9 in memory

• Value -11 would show 9
• Value -12 would show 8

And so on…

• Value 10 would show -10
• Value 11 would show -9