How integers are stored in memory using two’s complement in digital computers

Introduction

In digital computers, Complements are used in order to simplify the subtraction operation and for the logical manipulations. For the Binary number (base-2) system, there are two types of complements: 1’s complement and 2’s complement.

1’s Complement of a Binary Number:

There is a simple algorithm to convert a binary number into 1’s complement. To get 1’s complement of a binary number, simply invert the given number.

2’s Complement of a Binary Number:

There is a simple algorithm to convert a binary number into 2’s complement. To get 2’s complement of a binary number, simply invert the given number and add 1 to the least significant bit (LSB) of a given result.

From the above, a layman's language would mean that 1's complement is positive while 2's complement is negative.

Decoding 2’s Complement Numbers

How to convert a signed binary number in two's complement representation to an integer in base ten:

1) In a signed binary two's complement, first bit (leftmost) indicates the sign, 1 = negative, 0 = positive.

2) Get the signed binary representation in one's complement, subtract 1 from the initial number.

3) Construct the unsigned binary number: flip all the bits in the signed binary one's complement representation (reversing the digits) - replace the bits set on 1 with 0s and the bits on 0 with 1s.

4) Multiply each bit of the binary number by its corresponding power of 2 that its place value represents.

5) Add all the terms up to get the positive integer number in base ten

6) Adjust the sign of the integer number by the first bit of the initial binary number

Interesting consequence in 2’s complement arithmetic

In unsigned arithmetic a carry of the most significant digit means that there has been an overflow, but in signed arithmetic an overflow is not so easy to detect. In fact, signed arithmetic overflows are detected by checking the consistency of the signs of the operands and the final answer.

So in a nutshell, for one’s complement, we simply need to flip all bits.

For 2’s complement, we first find one’s complement. We traverse the one’s complement starting from LSB (least significant bit), and look for 0. We flip all 1’s (change to 0) until we find a 0. Finally, we flip the found 0. For example, 2’s complement of “01000” is “11000” (Note that we first find one’s complement of 01000 as 10111). If there are all 1’s (in one’s complement), we add an extra 1 in the string. For example, 2’s complement of “000” is “1000” (1’s complement of “000” is “111”).

How integers are stored in memory

In C, let's assume we wrote a piece of code to declare and initialize a variable with a (-)minus sign in front of its value, say:

int a = -34;

The question is how will this be stored in memory?

The theory is whenever a number with a minus sign is encountered, the number is converted to its binary equivalent and ignoring the (-)minus sign. Then the two’s complement of the number is calculated. The two’s complement is kept at place allocated in memory and a sign bit will be set to 1, which indicates or marks the binary being kept is of a negative number. To access that value firstly the sign bit will be checked and if the sign bit is 1 then the binary will be two’s complemented and converted to equivalent decimal number and will be represented with a minus sign, that is, the initially ignored (-)minus sign is returned. So what that means is that the CPU actually doesn’t know if a number is signed or unsigned, it only uses the above logic to somehow detect whether a number is negative or positive.

Let us see an example:

Example:

int num = -2056;

Binary of 2056 will be calculated which is: 00000000000000000000100000001000 (32-bit representation, according to the storage of int in C).

2’s complement of the above binary is: 11111111111111111111011111111000.

Finally, the above binary would be stored at memory allocated for variable num. When the value of the variable "num" needs to be accessed, the above binary would be retrieved from the memory location, then its sign bit, that is the leftmost bit would be checked. Since the leftmost sign bit is 1 in this example, the binary number is of a negative number so it would be 2’s complemented. Taking the 2’s complemented we get 11111111111111111111011111111000 for number 2056 with binary: 00000000000000000000100000001000

The above binary number would be converted to its decimal equivalent which is 2056 and as the sign bit was 1 so the decimal number which is being gained from the binary number would be represented with a minus sign. In our example -2056.

Voila!