Ever wondered how positive and negative integers are stored in the computer? I did that once, read a few answers on the Internet, and came to know that negative integers are stored in the two’s complement notation while positive integers are stored as is (in binary, of course). What I failed to do at that time is ask myself * Why*. Why exactly is it stored in that manner and how it helps, because it seems quite far from intuition. I try to answer the

*in this post.*

**Why**If you are not familiar with the binary representation of numbers or the two’s complement notation, don’t worry, I have tried to explain that as well.

**Binary Representation**

In mathematics and digital electronics, a **binary number **is a number expressed in the **binary numeral system **or **base-2 numeral system** which represents numeric values using two different symbols: **0 (zero) **and **1 (one).** Because of its straightforward implementation in digital electronic circuitry using logical gates, the binary system is used internally by almost all modern computers and computer-based devices. Each digit is referred to as a **bit***.*

Integer values are common data items. They are used in computer programs and computation all the time. We learn about them in math class and represent them using the decimal number system, or base 10. The decimal number **233 _{10} **and its corresponding binary equivalent

**11101001**are interpreted respectively as

_{2}`(2 x 10`^{2}) + (3 x 10^{1}) + (3 x 10^{0})

and

(1 x 2^{7}) + (1 x 2^{6}) + (1 x 2^{5}) + (0 x 2^{4}) + (1 x 2^{3}) + (0 x 2^{2}) + (0 x 2^{1}) + (1 x 2^{0})

But how do we get one from the other? The answer is an algorithm called “Divide by 2” that uses a stack to keep track of the digits for binary result.

The Divide by 2 algorithm assumes that we start with an integer greater than 0. A simple iteration then continually divides the decimal number by 2 and keeps track of the remainder. The first division by 2 gives information as to whether the value is even or odd. An even value will have a remainder of 0. It will have the digit 0 in the ones place. An odd value will have a remainder of 1 and will have the digit 1 in the ones place. We think about building our binary number as a sequence of digits; the first remainder we compute will actually be the last digit in the sequence. As shown in the following figure, we again see the reversal property that signals that a stack is likely to be the appropriate data structure for solving the problem.

**Computer Memory & Integer representation**

A n-bit storage location can represent up to 2^{n} distinct entities. For example, a 3-bit memory location can hold one of these eight binary patterns : 000, 001, 010, 011, 100, 101, 110, or 111. Hence, it can represent at most 8 distinct entities. You could use them to represent numbers 0 to 7, numbers 8881 to 8888, characters ‘A’ to ‘H’, or up to 8 kinds of fruits like apple, orange, banana; or up to 8 kinds of animals like lion, tiger, etc.

Computers use a fixed number of bits to represent integers. The commonly used bit-lengths for integers are 8-bit, 16-bit, 32-bit or 64-bit. We shall consider the 32 bit representation for the rest of this post. For example, the number 233 can be represented using 32 bits as follows:

0000-0000-0000-0000-0000-0000-1110-1001

**Signed Integers**

So now we know how to represent *positive* integers, it’s a good time to wonder how *negative *integers are represented in the computer. In ordinary usage, one uses a minus sign to designate a negative integer. However, a computer can only store information in bits.

An **unsigned*** integer *is either positive or zero. Consider a single digit decimal number: in a single decimal digit, you can write a number between 0 and 9. In two decimal digits, you can write a number between 0 and 99, and so on. Since 9 is equivalent to 10

^{1}– 1, 99 is equivalent to 10

^{2}– 1, etc, in n decimal digits, you can write a number between 0 and 10

^{n}– 1. Analogously, in the binary number system, an unsigned integer containing n bits can have a value between 0 and 2

^{n}– 1 ( which is 2

^{n}different values). Thus, with 32 bits, we can store numbers between 0 and 2

^{32}– 1 (4,294,967,295).

**Signed*** number representations* are required to encode negative numbers in binary number systems. The four best-known methods for representing signed numbers are : signed-magnitude, ones’ complement, two’s complement, and offset binary. I will avoid the discussion of offset binary in this post.

**Signed Magnitude Representation**

In this approach, the problem of representing a number’s sign can be solved by allocating one * sign bit * to represent the sign: setting that

*(often the most significant bit, or the MSB) to 0 is for a positive number and setting it to 1 is for a negative number. The remaining bits in the number indicate the magnitude (or absolute value). Hence, in a 32-bit memory location, with only 31 bits (apart from the sign bit), the magnitude can range from 0 to 2147483647 and the values can range from -2147483647*

**bit**_{10 }to 2147483647

_{10}. The extreme positive and negative values with the sign bit (MSB bit) in bold, are shown in binary below :

1111-1111-1111-1111-1111-1111-1111-1111_{2 }(-2147483647_{10})1000-0000-0000-0000-0000-0000-0000-0000_{2 }(-0_{10})0000-0000-0000-0000-0000-0000-0000-0000_{2}(+0_{10})0111-1111-1111-1111-1111-1111-1111-1111_{2}(+2147483647_{10})

Though this approach is directly comparable to the common way of showing a sign (placing a “+” or “-” next to the number’s magnitude), it has certain drawbacks.

First, it has two patterns that corresponds to 0 ( “plus zero”, and “minus zero”, which are shown above). Second, it does not work well in computation. A good representation method for integers must not only be able to represent the objects of interest, but must also support operations on those objects. This is illustrated with the following example. Consider addition using simple 32-bit signed magnitude integers. Consider adding 1 + 1

0000-0000-0000-0000-0000-0000-0000-0001_{2}(+1_{10})+0000-0000-0000-0000-0000-0000-0000-0001_{2}(+1_{10}) ------------------------------------------------0000-0000-0000-0000-0000-0000-0000-0010_{2}(+2_{10})

We see that we have arrived at the right answer when adding two positive integers. What happens when we try adding two negative integers? Consider (-1) + (-1)

1000-0000-0000-0000-0000-0000-0000-0001_{2}(-1_{10})+1000-0000-0000-0000-0000-0000-0000-0001_{2}(-1_{10}) ----------------------------------------------------1_{carry }0000-0000-0000-0000-0000-0000-0000-0010_{2}(+2_{10})

Since we are adding 32 bit integers, we discard the overflow bit, and we are left with +2_{10}. We got the magnitude of the sum correct, but not the sign. A naive solution would be to ignore the sign bit during the calculation, in which case (-1) + (-1) is :

1000-0000-0000-0000-0000-0000-0000-0001_{2}(-1_{10})+1000-0000-0000-0000-0000-0000-0000-0001_{2}(-1_{10})_{--------------------------------------------------------------------- }1000-0000-0000-0000-0000-0000-0000-0010(-2_{2}_{10})

We got -2, which is the correct answer. While this also works when adding two positive integers, we see that it’s not a viable solution when adding positive and negative integer. Consider (1) + (-1) :

0000-0000-0000-0000-0000-0000-0000-0001_{2}(+1_{10})+1000-0000-0000-0000-0000-0000-0000-0001_{2}(-1_{10}) -------------------------------------------------?000-0000-0000-0000-0000-0000-0000-0010_{2}(?2_{10})

Which sign bit do we preserve? Actually, it doesn’t matter, because the magnitude of the sum is 2, which is incorrect whether the sign is positive or negative. The answer should have been zero.

**Ones’ Complement**

Alternatively, a system known as ones’ complement can be used to represent negative numbers. The ones’ complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number. For example, +1 and -1 are represented as :

0000-0000-0000-0000-0000-0000-0000-0001_{2 }(+1_{10})

and

1111-1111-1111-1111-1111-1111-1111-1110_{2 }(-1_{10})

We notice that this scheme, like signed-magnitude representation, uses one bit to represent sign of the integer.

The primary advantage that ones’ complement notation has over signed-magnitude is the ease of carrying out operations. Adding two values is straight forward. Simply align the values on the least significant bit and add propagating any carry to the bit one position left. If the carry extends past the end of the word it is said to have “wrapped around”, a condition called “end-around carry”. When this occurs, the bit must be added back in the right most bit.

Consider 22 + 3

0000-0000-0000-0000-0000-0000-0001-0110_{2 }(+22_{10})+ 0000-0000-0000-0000-0000-0000-0000-0011_{2 }(+3_{10}) --------------------------------------------------0000-0000-0000-0000-0000-0000-0001-1001_{2 }(+25_{10})

The addition produces +25, which is the right answer. Now let us consider addition of two negative numbers : (-2) + (-2)

1111-1111-1111-1111-1111-1111-1111-1101_{2 }(-2_{10})+1111-1111-1111-1111-1111-1111-1111-1101_{2 }(-2_{10}) -------------------------------------------------------1_{carry }1111-1111-1111-1111-1111-1111-1111-1010_{2 }(-5_{10})

We see that the carry extends past the end of the word. We therefore have to add the carry back to the LSB, which gives the result as :

1111-1111-1111-1111-1111-1111-1111-1011_{2 }(-4_{10})

Which is the right answer.

Let us now consider adding a positive and a negative integer :

(+1) + (-1)

0000-0000-0000-0000-0000-0000-0000-0001_{2 }(+1_{10})+ 1111-1111-1111-1111-1111-1111-1111-1110_{2 }(-1_{10}) -------------------------------------------------1111-1111-1111-1111-1111-1111-1111-1111 (-0_{10})

Ones’ complement notation seems to work fine when doing arithmetic which signed-magnitude notation clearly failed at. But there is one major drawback to ones’ complement notation – Zeroes. The extreme values that can be fit in a 32-bit memory location when using ones’ complement notation are :

1000-0000-0000-0000-0000-0000-0000-0000_{2 }(-2147483648_{10})1111-1111-1111-1111-1111-1111-1111-1111_{2 }(-0_{10})0000-0000-0000-0000-0000-0000-0000-0000_{2 }(+0_{10})0111-1111-1111-1111-1111-1111-1111-1111_{2 }(+2147483648_{10}

We see that we are still stuck with multiple patterns for representing 0: +0_{10} and -0_{10,} which is undesirable.

**Two’s Complement**

The problems of multiple representations of 0 and the need for the end-around carry are circumvented by a system called two’s complement. In two’s complement, negative numbers are represented by the bit pattern which is one greater (in an unsigned sense) than the ones’ complement of the positive value.

In two’s complement, there is only one zero, represented by a sequence of 0s. Negating a number (whether positive or negative) is done by inverting all the bits and then adding one to that result. Addition of a pair of two’s-complement integers is the same as addition of a pair of unsigned numbers. The two’s-complement notation, like the ones we’ve discussed earlier for representing signed integers, uses one bit (the MSB) to denote the sign: 0 for positive and 1 for negative integers.

Consider the number -30. To represent it in 2’s complement, you take the binary representation of 30 :

0000-0000-0000-0000-0000-0000-0001-1110

Invert the digits

1111-1111-1111-1111-1111-1111-1110-0001 (One’s complement)

and add one.

1111-1111-1111-1111-1111-1111-1110-0010

Let us look at some examples to show two’s complement in action.

Consider addition of two negative integers : (-2) + (-2)

1111-1111-1111-1111-1111-1111-1111-1110 (-2_{10}, in 2’s complement) +1111-1111-1111-1111-1111-1111-1111-1110 (-2_{10}, in 2’s complement) -----------------------------------------1111-1111-1111-1111-1111-1111-1111-1100 (-4_{10}, in 2’s c)

Since MSB in the result is 1, we know that it’s a negative integer represented in 2’s complement notation. The magnitude is obtained by taking the 2’s complement of the result as done below:

1111-1111-1111-1111-1111-1111-1111-1100 (-4_{10}, in 2’s complement)

invert all the bits

0000-0000-0000-0000-0000-0000-0000-0011 (1's complement of result)

and add one

0000-0000-0000-0000-0000-0000-0000-0100 (+4_{10})

Let us now consider the addition of a positive and a negative integer : (+2) + (-2)

0000-0000-0000-0000-0000-0000-0000-0010 (+2_{10}) +1111-1111-1111-1111-1111-1111-1111-1110 (-2_{10}, in 2’s complement) -----------------------------------------0000-0000-0000-0000-0000-0000-0000-0000 (0_{10})

We see that two’s complement works similar to one’s complement without the drawback of multiple representation of zeros or keeping track of overflows.

**But it makes no sense!**

For those who wonder why inverting all bits and adding one for representing negative integers works and why it is so far from intuition, if you think about it deep enough, you realize that it actually is quite intuitive. Let me illustrate this with an example. Consider the integer (-30). 30 is represented in binary as:

0000-0000-0000-0000-0000-0000-0001-1110 (+30_{10})

by inverting all the bits in the representation for 30, we obtain the 1’s complement form which is

1111-1111-1111-1111-1111-1111-1110-0001 (1’s complement of +30_{10})

When we add the two, we obtain a sequence of only 1s :

0000-0000-0000-0000-0000-0000-0001-1110 + 1111-1111-1111-1111-1111-1111-1110-0001_{---------------------------------------------------------- }1111-1111-1111-1111-1111-1111-1111-1111

If we add 1 to this, we obtain 0

1111-1111-1111-1111-1111-1111-1111-1111 + 0000-0000-0000-0000-0000-0000-0000-0001 ------------------------------------------ 0000-0000-0000-0000-0000-0000-0000-0000

Therefore, for any number x, we have the following equation:

x + (~x + 1) = 0

Where ~x (NOT x) is all the bits inverted in the representation of x. Bringing x to the other side of the equation, we obtain

-x = (~x + 1)

Which is exactly how we obtain the 2’s complement of a number x.

**References**

- Wiki page on binary numbers

https://en.wikipedia.org/wiki/Binary_number - Converting between decimal and binary numbers

http://interactivepython.org/runestone/static/pythonds/BasicDS/ConvertingDecimalNumberstoBinaryNumbers.html - Representing integers in the computer

https://www3.ntu.edu.sg/home/ehchua/programming/java/datarepresentation.html - Drawbacks of Signed Magnitude representation

https://chortle.ccsu.edu/AssemblyTutorial/Chapter-08/ass08_13.html and http://www.neuraldump.com/2016/02/binary-signed-integers-signed-magnitude-shortcomings/ - Ones’ complement and its drawbacks

https://en.wikipedia.org/wiki/Ones%27_complement - Two’s complement

https://en.wikipedia.org/wiki/Signed_number_representations