**⌚ October 27, 2014**

If we can express signed values, such as +5 and -5, in decimal, can we do so in binary? Indeed we can!

Signed numbers are either positive or negative in value. If the number is preceded by a minus sign, then the number is negative. If no sign is present or if the number is preceded by a plus sign, then the number is positive.

-5 Negative 5 +5 Positive 5 5 Positive 5 (+ symbol omitted) -100 Negative 100 8 Positive 8

(The value zero has no sign because nothing is nothing. Therefore, +0 and -0 are pointless.)

We can express signed numbers in binary in the same way, but there are a few points to be aware of to ensure correct mathematical results.

Over time, a number of techniques have been developed for the representation of binary signed numbers. The most obvious technique is to reserve the most significant bit as the sign bit to indicate the sign of the value. If the sign bit is 1, then the number is negative, and if the sign bit is 0, then the number is positive.

0 = Positive 1 = Negative

1 0000011 -3 0 1000001 +65 ^ | Sign bit (MSB)

However, while this simple technique might be suitable for some applications, it is not entirely correct. We will see why in a moment.

## Signed or Unsigned?

There is no way to know if a byte is signed or not simply by looking at the bits. Context is key. Is 10000011 -3d or is it 131d? There is no way to tell. We must know ahead of time whether or not the byte is signed. The general rule is to assume a positive integer unless the byte is noted as signed.

## Signed Value Range

Both signed and unsigned bytes consist of eight bits, so both can represent 256 unique combinations of bits. However, the possible range of values is different between the two.

Unsigned byte: 8-bits: 0 - 255 Signed byte: -128 to +127 (Sign bit + 7 bits data)

When one bit is reserved for the sign bit, then there is one less bit available to store value information. This affects the range of positive values possible with a signed byte.

A regular, unsigned byte can represent 256 unique values from 0 to 255 because all eight bits are used to store number data. However, a signed byte consisting of eight bits only has seven bits available to store number data because one bit is reserved for the sign. This reduces the maximum positive value by half, but at the same time, almost an equal number of negative values can be represented.

Look at a signed and unsigned 3-bit group. How many unique combinations are possible for both and what are their value ranges?

Unsigned 3-bit Range: 0 - 7 111 7 110 6 101 5 100 4 011 3 010 2 001 1 000 0 Signed 3-bit (*) Range: -3 to +3 011 +3 010 +2 001 +1 000 0 101 -1 110 -2 111 -3

(*****) Did you notice why there are only seven values instead of eight? Eight combinations are possible, but only seven are shown because there is no such value as negative 0. This exposes a weakness in this simple sign system of reserving a bit for the sign bit.

## Limitations

The process of reserving a sign bit to indicate the sign is simple, but it is flawed and it is not enough to accurately represent a signed binary value because we encounter problems when performing arithmetic on signed binary numbers. Let’s use the signed numbers -3 (10000011) and +65 (01000001) to illustrate.

Suppose we want to algebraically add -3 and +65 together in binary.

10000011 -3 + 01000001 +65 -------------------

Remember, we cannot tell if a byte is signed or not merely by looking at it. We must know ahead of time if the bytes are signed or not. In this case, the bytes are signed because of context.

65 plus -3 produces +62. (65 – 3 = 62) In the signed binary system used so far, 62 should be represented as 00111110b. Therefore, if we convert 65 and -3 to binary and add, we should arrive at the same result.

10000011b -3d + 01000001b +65d --------------------- 11000100b -68d Incorrect

The result 11000100b represents -68 in this system, not the +62 we were expecting, so the answer is incorrect. Even if the sign bit is ignored during addition and we focus on the first seven bits, the result is still +68. This is because the addition is being performed on unsigned numbers even though a sign bit is present.

Computer scientists recognized this problem long ago and realized that the data bits must be altered to reflect negative numbers.

## Forming the Negative of Number

This is incredibly easy. To represent the negative of a positive number in binary, simply find its two’s complement. Review Lesson 12 for details. In short, first find the one’s complement and then add 1 to it to from the two’s complement. The result will be a negative version of the number.

00011001 Original byte (25d) 11100110 One's complement 11100110 + 1 Add 1 ----------------------------------------- 11100111 Two's complement (-25d)

11100111b (-25d) is the negative version of 00011001b (+25d). But how do we know for certain? We cannot convert 11100111b into decimal using a binary place value table or else we will arrive at an incorrect value. When dealing with negative binary, we are operating within the two’s complement system. 11100111b converted to decimal with the place value chart so far is +231d, not -25d.

## The Test

So, how can we test that 11100111b is the correct representation of -25d? Recall from math that the *additive inverse* of a number is that number, which, when algebraically added to itself, will result in zero.

For example, (+5) + (-5) = 0 and (+17) + (-17) = 0. In both cases, -5 and -17 are additive inverses, and 5 and 17 are additive inverses. -5 is the additive inverse of 5, and +5 is the additive inverse of -5. -17 is the additive inverse of 17, and +17 is the additive inverse of -17. The additive inverse is the opposite of a number.

The same applies to binary. To check if 11100111b is the binary additive inverse of 00011001b, add (in binary) 00011001 + 11100111 and ignore the ninth carry bit.

00011001 (+25d) + 11100111 (-25d) -------------------------- 1 00000000 ( 0d) ^ | Ignore the carry bit

There will be a carry bit one greater than the number of bits in the addends. Discard the carry bit and focus on the remaining bits. If they are all zero, then additive inverse is correct.

### What is -65d in binary?

Convert 65 to binary. We pad to eight places to form a byte.

65d --> 01000001b

Convert 01000001 to its one’s complement.

01000001 --> 10111110

Convert 10111110 to its two’s complement.

10111110 + 1 --------- 10111111 Two's complement

10111111b is -65d in binary.

01000001b = +65 10111111b = -65

### Check if 10111111b is -65d

How can we know for certain that 10111111b is -65d? After all, if we convert 10111111 to decimal, we get 191d (unsigned) or -63d using the simple sign system. Neither converts to -65d.

Look to math. We will review this concept again to demonstrate that the same additive inverse principle we use in decimal is applicable to binary.

If we add +65 to -65, the answer is 0.

+65 -65 ----- 0

The additive inverse is the opposite of a number, and when added to itself, the result is 0. To find the additive inverse of a number, simply flip the sign. This means that the additive inverse may be either positive or negative depending upon the sign of the original number.

(10) + (-10) = 0 | additive inverse of +10 (-5) + (5) = 0 | additive inverse of -5

Back to the binary. Since 10111111 (-65) is the negative or additive inverse of 01000001 (+65), we should be able to add the two addends together to produce 0.

01000001 +65 + 10111111 -65 ------------------ 1 00000000 0 | Carry bit. Discard.

The result produces a ninth carry bit outside the range of the byte representing the number. We must discard it because we must keep the resulting bit length the same as the original numbers when adding in the two’s complement system. Since the resulting byte is 00000000b, we know that 10111111b is the negative of 01000001b because a number plus its additive inverse equals 0.

By using the two’s complement system, all integers are considered signed. This allows the same addition process to be used for addition and subtraction. In electronic systems, one addition circuitry can be used perform both addition and subtraction provided integers are stored using the two’s complement system.

## Converting From Negative to Positive

So far, we have seen that the two’s complement forms the negative of a positive number in binary. What is really happening is that the two’s complement creates the additive inverse of a binary value. This means we can convert from positive to negative as we did earlier, and we can also convert from negative to positive using the same technique.

**Convert 11010110 (-42d) to its positive decimal value.**

11010110 original value. We know this is negative based on context. 00101001 one's complement 00101001 + 1 add 1 ------------ 00101010 two's complement

00101010b = 42d

We can use a place value chart for conversion if the binary value is positive. Check by adding the resulting byte to the original byte. The result should be 0. There will still be a carry bit, so ignore and discard it.

11010110 original (-42) + 00101010 result (should be +42) -------------- 1 00000000 ^ | Discard the carry bit

Since 00101010d (+42) is the additive inverse of -42, the sum is 0 when added together. This is how we know that 00101010 is +42. We can also convert 00101010 into decimal to confirm.

00101010b = 42d

## Range

Two’s complement automatically keeps track of the sign bit, but a sign bit is still being used. The maximum positive value of a signed byte is half the maximum positive value of an unsigned byte minus 1.

Unsigned: 0 to 255 Signed: -128 to +127

To calculate the range of a given two’s complement system, find the lowest and highest values separately.

**Highest value:**

2^(bit length - 1) - 1

**Lowest value:**

-[2^(Bit length - 1)]

We reduce the bit length in both cases by 1 to allow for the extra sign bit.

### 8-bit

**Highest Value:**

2^(8 - 1) - 1 = 2^7 - 1 = 128 - 1 = 127

**Lowest Value:**

-[2^(8 - 1)] = -[2^7] = -128

**Range:** -128 to 127

### 4-bit

**Highest:**

2^(4 - 1) - 1 = 2^3 - 1 = 8 - 1 = 7

**Lowest:**

-[2^(4 - 1)] = -[2^3] = -8

**Range:** -8 to 7

### 16-bit

**Highest:**

2^(16 - 1) - 1 = 2^15 - 1 = 32768 - 1 = 32767

**Lowest:**

-[2^(16 - 1)] = -[2^15] = -32768

**Range:** -32768 to 32767

The principle of representing integers using the two’s complement system is the same for any number of bytes. Recall in the simple signed 3-bit example that there was no negative for 0, so only seven of eight combinations of bits were possible. With two’s complement, all eight combinations are used.

Two's Simple ---------------------------------------- 011 +3 011 010 +2 010 001 +1 001 000 0 000 100111 -1 101 110 -2 110 101 -3 111 100 -4What goes here?

A 0 sign bit represents positive numbers, and a 1 sign bit represents negative numbers.

Notice that there are four negative values and three positive values. The range does not allow for -4 to +4 as might be expected because that would produce nine discreet values: -4, -3, -2, -1, 0, 1, 2, 3, 4, and three bits only allows eight unique combinations.

-1 is 111b, not 100b because the two’s complement of +1 (001) is 111b. There is no -0, so 0 is the only value without an additive inverse. This is the problem with the simple sign system, so 100b goes unused and the result is seven combinations instead of eight. This is why the data bits must be altered in addition to the sign bit.

Let’s look at how the two’s complement affects a 4-bit nibble.

Unsigned 1111 15 1110 14 1101 13 1100 12 1011 11 1010 10 1001 9 1000 8 0111 7 0110 6 0101 5 0100 4 0011 3 0010 2 0001 1 0000 0 Signed (Two's Complement) 0111 7 0110 6 0101 5 0100 4 0011 3 0010 2 0001 1 0000 0 1111 -1 1110 -2 1101 -3 1100 -4 1011 -5 1010 -6 1001 -7 1000 -8

## Handling Out-of-Range Numbers

Keep the number of bits and the value range in mind when converting. For example, suppose we wish to find the binary representation of -120d. An 8-bit byte has a range of -128 to 127, so -120d can be represented with eight bits of a two’s complement system. So far, so good.

Now, suppose we want to find the negative of 154d in binary. Can we do it? This answer is no, not with eight bits. 154d by itself cannot be represented in signed binary with only eight bits because the maximum value of a signed byte is 128, and 154d is greater than 128. We would need to add another bit to create a 9-bit storage system whose maximum signed value is +511d in order to convert.

If we try to convert 154d into negative without adjustment, here is what the result would be:

154d = 10011010 (8 bits) 10011010 --> 01100101 one's complement 01100101 + 1 add 1 ------------- 01100110 102d Incorrect.

One reason we can see that this is incorrect is because the sign bit is 0 instead of 1 as expected. We are trying to find the negative of the number in this case, and the most significant bit must be 1 for negative numbers. Since it is not and since the rest of the calculation was performed correctly, we know we do not have enough bits to represent 154d. The same applies when finding the positive of -154d.

**Check:**

10011010 + 01100110 --------------- 1 00000000 Check shows the correct result, but 01100110 is wrong.

01100110b is not the negative of 154d even though we performed the same two’s complement conversion as before and the addition check passed. One bit was missing, and that missing bit invalidated the entire calculation leading to an incorrect result.

Since 154d fits within a 9-bit value, pad an extra 0 to the MSB of the original positive byte.

10011010 (original 8 bits) --> 010011010 (9 bits)

With 010011010b, we can now obtain the correct result, so let’s try again.

154d = 10011010b = 010011010b (9 bits) 010011010 --> 101100101 one's complement 101100101 + 1 ----------- 101100110 two's complement (-154d)

**Check by adding:**

010011010 original 9 bits + 101100101 9-bit result ------------- 1 000000000 Correct | Discard the carry bit.

In most modern personal computers, signed numbers are handled automatically using 32-bit or 64-bit values, and programming constructs exist that will handle even larger numbers. The small number of bits presented are for demonstrating the principles.

## Simpler Two’s Complement Conversion

It will require some practice, but here is another way to find the two’s complement of a binary number:

**1.** From right to left, record each 0 bit until the first 1 is encountered. Record the 1 bit and proceed to step 2.

**2.** For the remaining bits after the first 1 encountered, record the complement of all remaining bits including the sign bit.

**Find the two’s complement of 11101000b.** Or to express it another way, what is the additive inverse of 11101000b?

From right to left, starting from the least significant bit, the 0 bits remain the same until the first 1 is encountered. Record all 0 bits and the first 1 bit as they appear.

11101000 |||| 1000

For the remaining bits, simply record their opposites.

11101000 |||||||| 00011000

Is 00011000b the additive inverse (two’s complement) of 11101000b? Add it to the original binary value to find out.

11101000 -24d + 00011000 +24d ------------ 1 00000000 Correct

We can also convert again using the long method to see if we obtain the same result.

11101000 --> 00010111 one's 00010111 + 1 add one ---------- 00011000 Correct match

## Beware of Overflow

Overflow happens when two numbers are added together and produce a sum greater than the number of bits available to represent the sum value. This is most apparent when adding values with like signs.

For example, adding +120 to +121 produces +241, but this is too large for seven bits to represent in a two’s complement system whose maximum positive value is +127 because the eighth bit is used as the sign bit.

01111000 +120 + 01111001 +121 ------------------------- 11110001 Incorrect

11110001b is correct as an unsigned byte, but it is incorrect in a two’s complement system because this represents -15d. During addition, the seventh bit was carried into the sign bit because the sum of 01111000b + 01111001b was too large for seven bits to represent. This results in overflow, and the same can happen for negative values.

**Converting +120d to -120d:**

01111000b (+120d) --> 10001000b (-120d) 10001000 -120 + 10001000 -120 ---------- 1 00010000 Incorrect

(-120) + (-120) equals -240, but we are left with the binary result of 00010000b because -240 is outside the range of -128.

The solution is to add an extra bit or group of bits so larger values can be stored. Adding two extra bits to produce a 10-bit system allows more room for growth and to accommodate larger values.

0001111000 +120 (10-bit) + 0001111001 +121 (10-bit) -------------- 0011110001 +241 (10-bit) Correct

1110001000 -120 (10-bit) + 1110001000 -120 (10-bit) ------------ 1 1100010000 -240 (10-bit) +240 = 0011110000b | Discard the carry bit. Result must be same bit length as original.

Overflow can also occur for unsigned bytes, such as 250 + 250.

11111010 250 + 11111010 250 ------------ 111110100 500 | Overflow or carry bit

The solution is the same: Use more bits. Know ahead of time the minimum and maximum values expected. Computers need to be told how to do *everything*, after all.

## Practice

1. Convert to one’s complement: 11000b

2. Convert to two’s complement: 110011b

3. What is -37d in binary?

4. What is the additive inverse of 512?

5. Is -8d represented as 11000b in binary?

6. Is -60d represented as 11000101b in binary?

7. What is -512d in binary?

8. 101000000b is -192d in binary. What is its additive inverse in binary?

9. What is the signed range of a 9-bit system?

10. Can +512 be stored in a signed 10-bit system?

11. How many unique value combinations are possible with a 32-bit unsigned system, and what is the maximum value that can be represented in it?

### Answers

1. 00111b (Simply invert all bits to find the one’s complement.)

2. 001101b. (Add 1 to the one’s complement or use the alternative method described above.)

3. 1011011b

Step 1: Convert 37 to binary. 37d = 100101b

Step 2: Since the MSB is 1, pad with a leading 0 to denote a positive value: 0100101b

Step 3: Convert 0100101b to its two’s complement: 0100101b –> 1011011b

Step 4: Check: 0100101b + 1011011b = 0b (Discard the carry bit.)

4. -512. 512 is positive, and the additive inverse is the number with its sign inverted.

When a number is added to its additive inverse, the sum is zero. (+512) + (-512) = 0

5. Yes. Convert -8d to binary to find out.

Step 1: 8d = 1000b. Pad with a leading 0: 01000b

Step 2: Find the two’s complement. 01000b –> 11000b (-8s)

Step 3: Compare and check. 11000b matches 11000b in the question, but to be certain, we must add 11000b (-8d) with 01000 (+8d) to see if the result is 0. (Discard the carry bit.)

01000b (+8d) + 11000b (-8d) -------------------- 1 00000 ^ | Discard the carry bit.

6. No. 11000100b is -60d in binary.

7. 11000000000b

Step 1: +512d = 01000000000b (We need an 11-bit system)

Step 2: -512d = 11000000000b (Two’s complement, which is the negative value)

8. 011000000b = +192d

Step 1: To convert from negative binary to its postive version, find the two’s complement.

101000000b (-192d) ---> 011000000b (+192d)

Since the two’s complement system involves signed values, we need nine bits to allow a range large enough to store +192d. (A signed 8-bit system is limited to +127d.)

9. A 9-bit signed system stores values -256 to +255.

10. No. While 512 can be stored in an unsigned 10-bit system, which has a range of 0 to 1023, 512 cannot be stored in a signed 10-bit system, which has a range of -512 to 511. We would nee an 11-bit signed system to store the value 512d.

11. Unique values: 0 to 4,294,967,296. Maximum value: 4,294,967,295. Analyzing a 4-bit unsigned system, think about why the maximum value possible is always one less than the total number of unique values.

(*Need a hint?* It is because we begin counting from 0.)