The leftmost bit in the representation of a signed integer is always the **sign bit**. A sign bit of 0 indicates a positive number; a sign bit of 1 indicates a negative number. There are several different schemes for representing negative numbers. The first that may come to mind is to find the base two representation of the absolute value of the number then put a 1 in the sign bit if the number is negative. Thus, the number -89 on a 16-bit machine would be represented as 1000000001011001 (89 is 1011001 in base 2). This is called the **sign and magnitude** representation of the number. While it seems straightforward it really isn't the best scheme. The problem comes in performing addition and subtraction on such numbers. Remember all the rules about adding signed numbers? There would need to be lots of tests of the sign bits to determine if the numbers were the same sign or not, then if they weren't a test would need to be done to determine which number was larger in absolute value. Too much work!! A much better representation scheme, and the most common one, is called **two's complement**. Two's complement representation uses an idea fundamental to basic arithmetic: the sum of a number and its negative is 0. In computer arithmetic, the sum of the two's complement representation of a number and the two's complement representation of its negative is 0 (in the computer).

**The n-bit two's complement representation of a positive integer is the base 2 representation of the integer with 0s added to the left to give a total of n-bits.**

**Example:** To find the 10-bit two's complement representation of 52 (base 10), first convert 52 to base 2 (you get 110100) then fill out on the left with 0's to get a 10-bit number. So the 10-bit two's complement representation of 52 is 0000110100.

**The n-bit two's complement representation of a negative integer** is based on two basic properties: the way computers add and the fact that -x (negative x) is the number you must add to x to get 0 (if x is 3, then -x is -3 because 3 + (-3) = 0 and if x is -4 then -x is 4 because -4 + 4 = 0).

Observe that if a 10-bit computer adds 0000110100 and 1111001100 it gets 0...

0 0 0 0 1 1 0 1 0 0 (52) + 1 1 1 1 0 0 1 1 0 0 ------------------- 0 0 0 0 0 0 0 0 0 0The 1 carried out of the leftmost bit is dropped - there is no room for it in 10 bits so the result is just 0. Thus the bit pattern 1111001100 is the 10-bit two's complement representation of -52.

Now we need to see where this comes from. One way to look at it is to think about how we add: we start on the right, adding bits and, if necessary, carrying to the next position to the left. So, if we start with one bit pattern (a number!) and want to find the two's complement representation of the negation of the number we just figure out what bit pattern added to the first one will give 0. This leads us to the first algorithm for finding the two's complement.

**Algorithm #1**: To find the n-bit two's complement representation of -m (where m is positive):

- Find the base 2 (binary) representation of m.
- Add the appropriate number of 0s to the left to get n bits total.
- Complement each bit to the left of the rightmost 1. (Complement means change 0 to 1 and 1 to 0).

**Observe**: If you take the two's complement bit pattern of any integer (positive or negative) and complement each bit to the left of the rightmost 1, you get the negation of the integer. For example, if we start with 1111001100 (which is -52) and complement each bit to the left of the rightmost 1 we get 0000110100 (which is 52 - the negation of -52).

Another way to think of the two's complement is as follows. In the addition above, if there were room for the carry bit, the sum would be 2^{10} = 1024. One further observation gives us a way to find the two's complement. Note that 1111001100_{2} = 972_{10} and 52 + 972 = 1024! So, the 10-bit two's complement representation of -52 is the base 2 representation of 2^{10} - 52 which is 972. In mathematical terms we say that 972 is the *additive inverse* of 52 *modulo* 1024 which means it is the number one must add to 52 to get 0 when using addition mod 1024 (add, then divide by 1024 and take the remainder as the answer). **An n-bit computer essentially uses arithmetic modulo 2 ^{n}** because its storage is limited to n-bits (throwing away carry bits is equivalent to dividing by 2

**Algorithm #2**: The n-bit two's complement representation of -m (where m is a positive integer) is the base 2 representation of the positive integer 2^{n} - m. In mathematical terms, this is the additive inverse of m modulo 2^{n}. So, to calculate it: Find the base 2 representation of 2^{n} - m.

**Algorithm #3**: A third algorithm, related to the first is often used. It is as follows:

- First, find the binary representation (base 2) of the absolute value of the number. Fill out the number to the appropriate number of bits with 0s in front.
- Next, complement each bit (change 0s to 1s and 1s to 0s) - this is called the
**one's complement**. - Finally, add 1.

(1) Find the 16-bit two's complement representation of -89.

__Using Algorithm #1:__

- Find the base 2 representation of 89 - which is 1011001
- Fill out with 0s to get 16 bits: 0000000001011001
- Complement each bit to the left of the rightmost 1: 1111111110100111

(2) Find the two's complement representation of -24 in 8-bits.

__Using Algorithm #2:__

- Find the base 2 representation of 24 - which is 11000
- Fill out with 0s to get 8 bits: 00011000
- Complement each bit to the left of the rightmost 1: 11101000

(3) Find the base 10 value of the 12-bit two's complement number 000001011011.

First note that this is a positive number because the sign bit is a 0. Hence, the only thing you need to do is convert the base 2 number 1011011 to binary - which is 64 + 16 + 8 + 2 + 1 = 91. So the base 10 value is +91.

(4) Find the base 10 value of the 12-bit two's complement number 111110010001.

- First note that this is a negative number because the sign bit is 1. Hence we must complement it to find the number it is the negative of.
- Find the two's complement (complement each bit to the left of the rightmost 1): 000001101111
- Convert the complement to base 10 - which gives 64 + 32 + 8 + 4 + 2 + 1 = 111. ANSWER: -111

1 1 1 1 0 0 1 1 1 1 1 1 + 0 0 0 0 0 1 0 1 1 0 0 0 ----------------------- 1 1 1 1 1 0 0 1 0 1 1 1Check: 111100111111 is negative so we complement each bit to the left of the rightmost 1 to get 000011000001. Now convert this to base 10: 128 + 64 + 1 = 193. Hence the base 10 number is -193.

000001011000 is positive so we just find its base 10 value: 64 + 16 + 8 = 88

Finally the sum 111110010111 is negative so we complement - 000001101001 - and convert - 64 + 32 + 8 + 1 = 105. Hence the sum is -105.

Thus we have -193 + 88 = -105 which is correct!

(6) Add the following 12-bit two's complement numbers and check the work.

0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 ----------------------- 1 0 1 1 1 0 0 0 1 0 1 0Without doing any work we know something strange happened!! Two positive numbers were added but the sum is negative!

- 1000112
- 10111000102
- 45318
- B32F16
- 4221305

- 100110111
- 10111011110101

- binary
- hexadecimal

- binary
- octal

- 528
- 4269
- 341

- 6 bits
- 12 bits
- 32 bits

- -198
- 37
- -37
- -5,235
- 9,102
- -9,102

- 01110011
- 10001001
- 11011110
- 00000111
- 11111111

- 2,548
- -5,377