How can we encode negative numbers? Well, we could set aside one bit
that indicates whether the number is negative or positive. Say we did
this. Then we would have: negative: 0 .. 2^31-1 and positive: 0
.. 2^31-1. This is called **signed integer notation**. So we
are close, except that we have a **negative zero and a positive zero**.
Most computer designers don't like that (though some computers have been
built with this scheme). It seems clear that if all bits are zero, the
number should be zero, and if the sign bit is set the number should be
negative. So what about 10...0? Hmmm. We have a slight problem here.

Another issue arises. We would like **addition to work the same** whether it
involves two positive numbers, a positive and a negative, or two negative
numbers. Clearly, adding +2 and -2 when they are in signed-integer
notation does not yield 0.

It turns out that with a proper representation of negative numbers, we can:

- avoid the two-zero problem;
- implement addition consistently regardless of the signs of the operands; and
- implement subtraction using the addition units.

The drawback is that the representation is rather strange (until you get used to it!)

What number should we add to 1, if we are want to get zero as the
result, and are willing to throw away the carry-out bit? Answer:

00..01 + 11..11 = 00..00

So we could call 1..11 "-1" since in that case 1 + (-1) = 0. Likewise,

00..10 + 11..10 = 00..00 so 11..10 is "-2".

So, looking at bit patterns and the numbers they represent:

00..00 = 0 00..01 = 1 00..10 = 2 ... 01..10 = 2^31-2 01..11 = 2^31-1 10..00 = -(2^31) 10..01 = -(2^31-1) ... 11..10 = -2 11..11 = -1Can you find a relationship between a number (say, 2) and its complement (-2)? Well, note that the logical bit-flip of -2 is 1. Likewise, of -3 is 2.

The subtraction of a binary number from a bit pattern of all 1's is the
same as a logical inversion of all bits. So subtracting from all 1's is
called **one's complement**. **Two's complement** is just one's
complement plus one.

How do we convert from negative to positive, or vice versa? The simple
rule of thumb is "**flip the bits and add one**". Memorize this. This
representation for integers is called "**two's complement**".

Let's use examples in base 2^8 (explain about sign extension). What's the representation, one's complement, and two's complement of: 0, 64, -64, -127, 127?

Characteristic of two's complement is that a number that is larger than
(2^31-1) appears to be negative. This is another example of **overflow**.
In this case, ignoring overflow would mistake a negative
number for a large positive one. Also, we could add two negative
numbers and get an apparently positive one, another example of a bad
overflow.

This is why there is a **V flag** in the processor. The V (overflow) flag
is set whenever the result of the computation is **too large (in absolute
value)** to be held by the register.

1's complement of a number b = (2^n - 1 - b )

e.g. 1's complement of 11 (when there are 4 bits, i.e. n = 4) :

11 = 1011 (in binary) One's complement = 16 - 1 - 11 = 4 = 0100 (binary)

Hence, we can see that the 1's complement of a number is another number with it's digits reversed, i.e , the digits are toggled (0 replaced by 1 and vice versa).

Similarly, 2's complement of a number b = (2^n - 1 - b ) + 1

e.g. 2's complement of 13 (when there are 4 bits i.e. n = 4),

13 = 1101 (in binary) Two's complement = 16 - 1 - 13 + 1 = 3 = 0011 (in binary)

**Other Examples: **

Again assuming n = 4, 2's complement of 11(1011) is 5(0101) 2's complement of 7(0111) is 9(1001)

Thus, it can be seen that the **2's complement of a number is a
number with the digits reversed, starting from the digit after
the rightmost 1** (all to the right of the rightmost 1, including
itself, remain unchanged).

Both 1's complement and 2's complement of a number can be used to perform subtraction.

where r is the base and n is the number of digits in the register

2's complement of a number b is equal to (2^n - 1 - b ) + 1.

So, **(a-b) can be written as : = a + (2's complement of b)**. e.g.

11 - 7 = (1011) - (0111) = (1011) + (2's complement of 0111) = 1011 + 1001 = 0100 (carry out is ignored) = 4 (decimal)But if no carry out, then the answer is negative, and is the

4 - 15 = (0100) - (1111) = (0100) + (2's complement of 1111) = 0100 + 0001 = 0101 As no carry out, the answer is 2's complement of the result, i.e. (2's complement of 0101) = 1011 = -11 (decimal).

Hence, 1's complement and 2's complement are quite similar...but which one is preferred???

**Ans:** 2's complement, as in that case, there is one less addition
involved, and the logic for it is easier to implement.

The **condition codes** when instructions are represented as 2's
complement are as follows:

- Z - when all bits are 0
- N - most significant bit is 1
- V - set when sign of minuend and subtrahend differ, and the result is same sign as the subtrahend

Instruction Condition codesbl (N xor V) = 1 ble (Z or N xor V) = 1 be (Z = 1) bne (Z = 0) bge (N xor V) = 0 bg (Z or (N xor V) = 0

sll reg, reg(imm.), reg - Shift left logical srl reg, reg(imm.), reg - Shift right logical sra reg, reg(imm.), reg - Shift right arithmeticLogical shift - Shift left or right, with zero copied in the end.

Arithmetic shift - Left shift same, hence there is no separate instruction, but on a right shift, sign bit is copied into the most significant bit position.

e.g. with 4 bits, we can represent numbers from 0 (0000) thru 15 (1111).

In case of subtraction, we can assume an extra bit which might represent the sign.

e.g. For calculating 10 - 3 (assuming 4 bits) :

10 - 3 = 1010 - 0011 = 01010 - 00011 = 01010 + 2's complement of 00011 = 01010 + 11101 = 00111 = 7 (decimal)

Instruction Condition codes blu C = 1 bleu Z = 1 or C = 1 beu Z = 1 bneu Z = 0 bgeu C = 0 bgu Z = 0 and C = 0There are also a set of instructions that test individual condition codes:

Instruction Condition codes Synonym Instruction bneg N = 1 bpos N = 0 bz Z = 1 be bnz Z = 0 bne bvs V = 1 bvc V = 0 bcs C = 1 blu bcc C = 0 bgeu

**Example of multiplication:** Multiply 3 an 5 , 3 in %o2, 5 in %o0

mov 3, %o2 mov 5, %o0 mov %o0, %y (special register, initially holds multiplier, nop finally the lower part of the product) nop nop (three nop as it takes time to store in %Y) andcc %g0, %g0, %o1 ! partial product = 0, clear N & V mulscc %o1, %o2, %o1 ! 32 times this instruction mulscc %o1, %g0, %o1 ! final shift mov %y, %o0

What do we do to the value of a number if we shift its representation left one place? All the bits occupy positions with one-higher place value, so the number has been multiplied by 2. What about if we shift it left 3 places?

The instruction is called `sll`, for shift left logical.

sll reg, reg_or_imm, regThe largest shift possible is 31.

What are the dangers of using `sll` for multiplication? What if we sll
an integer that is greater than 2^30-1 ? And what about negative
numbers?

**Note:** shift instructions do not modify the condition codes. You are on
adjust: Command not found.
OK, if left-shifting is equivalent (dangerously!) to multiplication by a
power of two, what is the effect of right-shifting? Consider first
positive numbers. Obviously, division. In fact, a trucating integer
division by 2. What about for negative numbers? Doesn't work at all,
but this time we have a solution: **sign extension**.

**Sign extension** means the filling-in of high-order bits based on the sign
bit. So we have two versions of the right shift: `srl` (logical) and `sra`
(arithmetic). The arithmetic version performs sign extension. The
logical version fills in with zeroes, like the `sll` instruction.