Computer Theory: Signed Integers

**John** · 11-29-2008, 10:47 AM

Anyone who has taken an hour or so to read through the first few chapters of any programming book has come across data types. There are several data types, which sometimes depend on the language you use, but generally speaking, there are four popular primitive data types supported by most popular languages and they are integers, chars, doubles, and floats. Of course some languages support support other primitives, and if you extend the list beyond primitives we can talk about arrays, lists, vectors, trees, and the list goes on. For the purpose of this tutorial, we will be discussing integers, more particularly, the differences between signed and unsigned integers.

Binary
When you get down to the lowest level of programming, computers only understand two things: 1 and 0. For those of you not familiar with this concept, those ones and zeros are bits (binary digits). For practical purposes, bits are strung together to form larger binary numbers: 1001010.

Since binary is a base-2 system, each digit represents an increasing power of 2, with the rightmost digit representing 2⁰, the next representing 2¹, then 2², and so on. To determine the decimal representation of a binary number simply take the sum of each of the product binary digits with the power of 2 which they represent.¹

Therefore to convert the example above, 1001010, we start from the right zero (least significant bit - LSB). The value at the a particular location becomes the multiplier. (I will represent the bit in bold and the power/location will be red)

(0*2⁰)+(1*2¹)+(0*2²)+(1*2³)+(0*2⁴)+(0*2⁵)+(1*2⁶)
which becomes:
(0*1)+(1*2)+(0*4)+(1*8)+(0*16)+(0*32)+(1*64)
that becomes
(2)+(8)+(64) = 74

Binary Addition
Now that we know how binary numbers are converted, binary addition is an essential operation in the representation of signed integers. At this point, we will take a short detour and learn how to add two binary numbers.

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 ( 1 + 1 is 2 and 2 in binary is 10)
1 + 1 + 1 = 11 ( 1 + 1 + 1 is 3 and 3 in binary is 11)

When adding more than one bit, the operation is essentially the same, however you must take into account carries, and by that, you must add the carries as you would any other bit.

Code:

         carry <----v  v----> sum
Bit 1:      1 + 0 = 0₁ 1
Bit 2: 0₁ + 0 + 1 = 0₂ 1
Bit 3: 0₂ + 0 + 1 = 0₃ 1
Bit 4: 0₃ + 1 + 0 = 0₄ 1

          0000     (carried bits)
  9  --->  1001
 +6  ---> +0110
----      -------
 15        1111

In the example above, 0 is carried in every case. Lets look at an example where there is a carry of one:

Code:

         carry <----v  v----> sum
Bit 1:      1 + 1 = 1₁ 0
Bit 2: 1₁ + 0 + 0 = 0₂ 1
Bit 3: 0₂ + 1 + 0 = 0₃ 1
Bit 4: 0₃ + 0 + 0 = 0₄ 0

          0001     (carried bits)
  5  --->  0101
 +1  ---> +0001
----      -------
  6        0110

In this case, when the first two bits are added (1+1) it results in 10. The zero is placed in the sum and the one is carried. The carry is then added to the next bits (1+0+0) which results in 1 and a carry of zero. This iterative process continues until you finish. Lets look at one more example with multiple carries:

Code:

         carry <----v  v----> sum
Bit 1:      1 + 1 = 1₁ 0
Bit 2: 1₁ + 1 + 1 = 1₂ 1
Bit 3: 1₂ + 1 + 1 = 1₃ 1
Bit 4: 1₃ + 0 + 0 = 0₄ 1

          0111     (carried bits)
  7  --->  0111
 +7  ---> +0111
----      -------
 14        1110

Signed Integers
Signed integers are what they sound like - integers with a sign (a plus or minus sign). Since most digital systems use binary, they do not have the ability to use a minus sign to represent a negative number. Using binary there are several methods to represent signed integers which are described below:

Sign Magnitude
The natural choice for representation is to use a one and a zero which represent a negative and a positive respectively. This is perhaps the easiest method for people to understand. Using this method, the left most bit (most significant bit - MSB) represents the sign. As previously mentioned, one representing a negative number and two representing a positive number. Also you need to keep in mind the amount of bits you are using as it can significantly change the meaning.

Examples:
1. Represent 33 as an an eight bit binary number.
In binary 33 gets converted to 100001. However that is only a six bit integer. Since prepending zeros to a binary number does not change the value, that is what we do. 00100001. Now notice that the MSB is a zero which means, that number represents positive 33.

2. Represent -54 as an eight bit binary number.
In binary 54 gets converted to 110110. To represent it as an eight bit integer we prepend two zeros. 00110110. However as, the MSB is a zero which means this is a positive 54, to represent a negative 54 we complement the MSB and end up with 10110110.

One's complement
This method is generalized to r-1's complement where r is the base. However since we are in binary (base being two) it is simply referred to ones complement. It should be noted that this method holds true for any base (9's complement for decimal). To convert we simply apply the formula r-1-a_i where a_i is a bit.

Example:
1. Convert the binary number 01101100 to ones complement notation.
Starting from the LSB we have:
2-1-0 = 1 (LSB)
2-1-0 = 1
2-1-1 = 0
2-1-1 = 0
2-1-0 = 1
2-1-1 = 0
2-1-1 = 0
2-1-0 = 1 (MSB)
Our final answer is 10010011. If you notice (in binary) to take the one's complement all you need to do is flip every bit.

2. Represent 33 as an an eight bit binary number in one's complement notation.
From a previous example 33 gets converted to 00100001. Since 33 is positive there is no need to represent it in one's complement. (I tricked ya)

3. Represent -54 as an an eight bit binary number in one's complement notation.
First we convert the positive integer (54) into an eight bit binary number - 00110110. Next we take the one's complement: 11001001.

Two's Complement
This method is generalized to r's complement. This is possibly the most difficult method, and just so happens to be the method most digital systems use. How come? Well, an issue inherent in the previous examples is the ability to have both a positive and negative zero. Using 4-bit sign magnitude notation 0000 represents zero, as does 1000. Using one's complement 0000 represents zero, as does 1111. Moreover, on a hardware level, two's complement becomes a lot easier to implement. That said, how is it done? The computation is done as you would one's complement, however once all the bits are flipped, an additional one is added. This extra one removes the possibility of two representations of zero.

From our previous example the binary number 01101100 in twos complement is 10010011. From where we add one:

Code:

0 0 0 0 0 0 1 1
  1 0 0 1 0 0 1 1
+ 0 0 0 0 0 0 0 1
-----------------
  1 0 0 1 0 1 0 0

A shortcut to manually convert a binary number into its two's complement is to start at the least significant bit (LSB), and copy all the zeros (working from LSB toward the most significant bit) until the first 1 is reached; then copy that 1, and flip all the remaining bits. This shortcut allows a person to convert a number to its two's complement without first forming its ones' complement. For example: the two's complement of "0011 1100" is "1100 0100", where the underlined digits are unchanged by the copying operation.²

¹ Binary numeral system - Wikipedia, the free encyclopedia
² Two's complement - Wikipedia, the free encyclopedia

**phpforfun** · 11-29-2008, 10:58 AM

very interesting tutorial, I was always wondering how a computer was able to convert binary into.. anything, I had no idea there are multiple methods.

+rep

Edit: I guess I have given you rep before, it wont let me, lol