The 2-complement method theory

As you know, computers are manipulating bits, 0 or 1. Therefore, any type of datas is represented by a series of 0 or 1.

The next table shows the value range and storage size of various kind of variables in C language.

In this article, we will focus on the way that Integers are stored

The most common method for storing integers is the 2’s complement method which allows :

• to have a unique representation for the 0
• to be able to store any integers between -2^(N- 1) and 2^(N -1) -1, when using N bits to encode integers
• to have fundamental arithmetic operations of addition, subtraction, and multiplication identical to those for unsigned binary numbers

The idea is based on the following simple formulae :

The representation of an integer i is the unique set of the N bits a(i) : the first bit is the only one which has a negative impact. It is usually called, the “sign bit”.

It has to be noted that, if we encode unsigned integers (meaning integers which are always positive), the first bit is not negatively signed and therefore, we can encode a range from 0 to 2^N -1.

The reason why this method is called “2-complement” comes from mathematics and is based on ways of making subtraction simpler when you have limited number places. So, let’s play a bit with binary numbers stored with this method

Let’s play with binary representation

Let’s see a couple of example for signed integers, assuming we code integers on 8 bits (in most of the systems integers are usually stored on 32 bits, but for the sake of understanding we’ll assume N = 8)

• 0 is coded as 0000 0000
• 1 is coded as 0000 0001
• The maximum positive int is : 0111 1111 -> 127
• The minimum negative int is : 1000 0000 -> -128
• 42 is coded as 0010 1010

Integer Max and Min :

• The biggest number we can obtain is : 0111 1111 = 127
• The lowest number we can obtain is : 1000 0000 = -128

Opposite of an integer : -i = ~i + 1

There are three steps necessary to convert a negative decimal integer to two’s complement form:

1. Start with the positive binary value, expanded to fill the number of bits you will be storing the number into.
2. Complement/flip all of the bits. This means all of the 1s become 0s and all of the 0s become 1s
3. Add one to the flipped bits.

• 42 = 0010 1010
• Inverting the 0 and the 1, we have 1101 0101 which is -43
• -42 is therefore 1101 0101 + 1 = 1101 0110
• Reciprocally, if we invert -42, we get 0010 1001 +1 = 42

Addition of 2 integers :

• 42 + 56 = 0010 1010 + 0011 1000 and 98 = 0110 0010 : the addition of 2 positive integers is the bit addition
• 42 – 42 = 0010 1010 + 1101 0110 = 0000 0000 : by construction, adding a number and its opposite gives back 0
• 56 – 42 = 0011 1000 + 1101 0110 = 0000 1110 = 14

Representation of -1

• -1 = 1111 1111 : it is the opposite of 0000 0001 + 1, using the method above

Overflow operation :

• 127 + 1 = 0111 1111 + 1 = 1111 1111 = -128 : this is called overflow

Bitwise operators

In C language, it is possible to transform directly integers stored as bit using the bitwise operators in the table above.

In general cases, it is not easy to interpret directly the effect of these operators in decimal numbers, but there are a couple of understandable cases:

• (i) & 1 : equivalent to i % 2
• i >> 1 : equivalent to i / 2
• i << 1 : equivalent to i * 2