Tutorial 3

CSE 112 Computer Organization

Ans 1:
a) Number = 1001100, Number of bits = 7
i) Unsigned representation = 1 * 26+ 0 * 25+ 0 * 24+ 1 * 23 + 1 * 22+ 0 * 21+ 0 * 20 = 76
Max value = 27- 1 = 127 (All bits are 1)
Min value = 0 (All bits are 0)
ii) Signed magnitude: We use the first bit as the sign of the number. For the given binary
number, the first bit is 1, which means that the number is negative. We use the other bits to
represent the magnitude of the number like an unsigned number.
Sign = negative
Magnitude = 0*25+ 0 * 24+ 1 * 23+ 1 * 22+ 0 * 21+ 0 * 20= 12
Number = -12
Max_value = 26-1 = 63
Min value = -(26-1) = -63
iii) 2’s complement representation: We can see the number is negative as the most significant bit
(MSB) is 1. To find its decimal value, we compute the magnitude by taking 2’s complement (invert
bits + 1).
Steps:​
invert bits of 1001100 → 0110011​
add 1 → 0110100.
2’s complement (1001100) = 0110100
Sign = Negative
Magnitude = -(0 * 26+ 1 * 25+ 1 * 24+ 0 * 23+ 1 * 22+ 0 * 21+ 0 * 20) = -52
Max value = (26- 1) = 63 (first bit 0 all other bits 1)
Min value = -(26) = -64 (first bit 1 all other bits 0)

b) i) Unsigned representation = 12
Max value = 127 (All bits are 1)
Min value = 0 (All bits are 0)
 ii) Sign = positive
Magnitude = 0*25+ 0 * 24+ 1 * 23+ 1 * 22+ 0 * 21+ 0 * 20= 12
Number = 12
Max_value = 26-1 = 63
Min value = -(26-1) = -63
iii) 2’s complement representation: We can see the number is positive as the most
significant bit (MSB) is 0 . We can directly find the value in decimal representation.
Sign = Positive.
Magnitude = +(0 * 26+ 0 * 25+ 0 * 24+ 1 * 23+ 1 * 22+ 0 * 21+ 0 * 20) = 12
Max value = (2^6 - 1)= 63 (first bit 0 all other bits 1) .
Min value = -(2^6) = -64 (first bit 1 all other bits 0).
c) It is not possible to uniquely determine the decimal value of a binary number unless the
representation is specified (Unsigned / Signed Magnitude / 2’s complement). Because the same bit
pattern can represent different values under different representations.

Ans 2:
a)​ 01010
b)​ 001010
c)​ 10110
d)​ 110110
Suppose a number can be represented by k bits in 2’s complement notation. Then the same
number can be represented by m+k (m > 0) bits by simply making the m MSBs the same as the kth
bit. This is called sign extension.
NOTE for the TAs : The objective of this question is to familiarize students with sign extension,
which is required in the next question. Please discuss how this concept applies to variable
casting as well. For example, how an 8 bit value is casted to 32 bits.

Ans 3: Number = 20
a)​ Unsigned Representation:
●​ 20 in binary : 10100
●​ Minimum bits = 5
b)​ Signed magnitude:
●​ Sign = 0 (positive)
●​ Magnitude = binary(20) = 10100
●​ So signed magnitude = 0 10100
●​ Minimum bits = 1 + 5 = 6
Signed magnitude(20) = 010100, min bits 6.
c)​ 2’s complement: Positive, so same bits as unsigned, but must have a leading 0 if we are
comparing with signed forms.
2’s complement (20) = 010100, min bits 6.

(2) Number = -20

a) Unsigned: Not possible (unsigned can’t represent negative).
Unsigned(-20): Not possible
b) Signed magnitude
●​ Sign = 1
●​ Magnitude = binary(20) = 10100​
So signed magnitude (-20) = 1 10100 = 110100​
Minimum bits = 1 + 5 = 6
Signed magnitude(-20) = 110100, min bits 6.
c) 2’s complement: We need enough bits first. For 20 we used a 6-bit signed as 010100.
Steps (6-bit):
+20 = 010100
invert bits → 101011
add 1 → 101100
So -20 in 6-bit 2’s complement = 101100
Minimum bits: As -20 cannot fit in 5-bit 2’s complement range as the 5-bit range is -16 to +15.
And the 6-bit range is -32 to +31, So min bits = 6.
2’s complement(-20) = 101100, min bits 6
(3) Number = 32
a)​ Unsigned Representation:
●​ 32 in binary = 100000
●​ Minimum bits = 6 (since 32 needs one more bit than 31).
Unsigned (32) = 100000, min bits 6.
b)​ Signed magnitude:
●​ Sign = 0
●​ Magnitude = 100000 (that’s 32)​
So signed magnitude (32) = 0 100000 = 0100000​
Minimum bits = 1 + 6 = 7
Signed magnitude(32) = 0100000, min bits 7.
c) 2’s complement: For 6-bit 2’s complement, the range is −32 to +31. Since 32 is greater than
d +31, it cannot be represented in 6 bits. So we need 7 bits.
2’s complement(32) = 0100000, min bits 7.

(4) Number = -32

a)​ Unsigned: Not possible.
b)​ Signed Magnitude:​

●​ Sign bit = 1,
●​ magnitude of 32 = 100000​
So, Signed Magnitude(−32) = 1 100000 = 1100000​
Min bits = 7

c)​ 2’s Complement :​

+32 = 0100000​
Invert bits → 1011111​
Add 1 → 1100000

Select last repeating 1 from MSB till LSB.

So, 2’s complement(−32) = 100000, min bits = 6

NOTE for the TAs: In 2’s complement notation, repeated MSBs are redundant.
 For example: 1001 in 2’s complement 4-bit notation
= 11001 in 2’s complement 5-bit notation
= 111001 in 2’s complement 6-bit notation
… and so on.
Therefore, to find the minimum number of bits for representation, we can take the bits from the
last repeating MSB till the LSB, which is 1001.

Ans 4 :
a) Each character in the sequence can take one of k symbols. Therefore for a sequence of length
n we can have at max kn different numbers.
b) We clearly need m values to represent each number in the set uniquely. A k-ary system
sequence with q characters can represent at max kq different values. Therefore we need the
smallest q, which satisfies kq > = m. This means that q = ceil(logkm).
For instance, if we are working with a 4-ary system (k = 4), then we have 4 symbols: 0, 1, 2 and
3. Now suppose the m = 20. Therefore we need a sequence of length 3 (ceil(log420) = ceil(2.16) =
3). With length 3 we can uniquely identify 43= 64 different elements. With length 2 we can
uniquely identify 42= 16 different elements. Since we need to identify 20 elements, we need at
least a 3 length sequence.
c) As k increases, we will need shorter and shorter sequences. Therefore the length decreases. For
instance, binary sequences are longer than their corresponding decimal notation.
d) In most computer systems, different symbols are represented by different voltage levels. To
distinguish between these symbols, we need to distinguish between different voltage levels. It is
considerably easier to do this when we have just two symbols. A valid representation for such a
case can be: GND for 0, and some non-zero voltage for 1 (and vice-versa). As we increase the
number of symbols, the difference in voltage levels between two successive symbols decreases (for
a fixed highest possible voltage), which increases the possibility of misrepresentation.

Ans 5 : A k bit 2’s complement notation can represent 2k different numbers, whereas signed
magnitude can represent 2k-1 different numbers. This is because in signed magnitude notation,
there are two symbols for 0, which represent +0 and -0. In arithmetic, 0 has no sign. Therefore,
multiple representations for 0 can be seen as a disadvantage for signed magnitude notation. A
weighted number system uses a weighted sum to represent a number. An example of a weighted
system is the decimal system.
For example: If you have the number 123 in decimal, 1 is weighted with 100, 2 is weighted with
10 and 3 is weighted with 1, i.e. 123 = 1 * 100 + 2 * 10 + 3 * 1. The weights are well-defined for
each position.
Whereas, 2’s complement is a weighted system. Weights of a n bit 2’s complement number are
-(2n-1), 2n-2,…., 21, 20.
Example: Let’s consider an example of 4 bit 2’complement number 1111 = 1 * -(23) + 1 * 22+
1 * 21+ 1 * 20= -1.
The sign bit is “unweighted”; the magnitude bits are still weighted powers of 2. Now let’s try
to figure out other properties of the 2’s complement system, such as how sign extension work:
Suppose, n = bx-1 * -(2x-1) + bx-2 * 2x-2+ … + b1 * 21+ b0 * 20, where bi is the ith bit in the 2’s
complement notation of n.
Suppose we sign extend it by k bits.
bx-1 * -(2x+k-1) + …. + bx-1 * 2x+ bx-1 * 2x-1+ bx-2 * 2x-2+ … + b1 * 21+ b0 * 20
= bx-1 * {-(2x+k-1) + …. + 2x+ 2x-1} + bx-2 * 2x-2+ … + b1 * 21+ b0 * 20
= bx-1 * 2x-1{-(2k-1) + 2k-2 + …. + 21+ 20} + bx-2 * 2x-2+ … + b1 * 21+ b0 * 20
= bx-1 * 2x-1{-(2k-1) + 2k-1- 1} + bx-2 * 2x-2+ … + b1 * 21+ b0 * 20
= bx-1 * 2x-1{- 1} + bx-2 * 2x-2+ … + b1 * 21+ b0 * 20
= bx-1 * -(2x-1) + bx-2 * 2x-2+ … + b1 * 21+ b0 * 20
=n
NOTE for the TAs: The last part is just for extra information. Please see to it accordingly.

Ans 6 :
If we add 01111111 + 00000001 then there will be an overflow. Since registers are only 8 bit wide,
therefore the largest number we can store is 27-1 = 127. However, we are computing 127 + 1 (=
128), which requires 9 bits in 2’s complement notation. As a result, this computation will overflow
and will generate 10000000 = -128, the wrong answer. This happened because we needed more
than 8 bits to store the result of the operation in 2’s complement notation. That’s why the result in
Z will not be correct. 128 has the representation of 010000000. Z will take the 8 LSBs of this, i.e.
10000000. You can detect this by checking for overflows. This can be done easily by looking at the
signs of the operands and the sign of the result. If they do not make sense, then there was an
overflow.
For example: In this case, the sign of both the operands was +ve, but the sign of the result was -
ve. This does not make sense.
Most ISAs have a special register, often called the flags or the status register, which tracks the state
information of the machine. A part of this state can be whether the last operation overflowed or
not. In such a case, the flags register can have a bit dedicated to detecting overflows. If the bit is set
to 1, this means the last operation overflowed (or vice-versa).
Ans 7 :
a) The highest possible sum is d x (2n-1) (at worst). This can be represented in ceil(log2(d x (2n-1)))
= n + ceil(log2d).
For example : If we add four 2-bit binary numbers 11 + 11 + 11 + 11 = 3+3+3+3 (in decimal), we
d get 12. We need 4 bits to represent 12 (2 + ceil(log2(4))).
b) We can consider the multiplication of two n and m bit numbers as (2m-1) (at worst)
repeated addition of n bit numbers. Therefore, we need n + ceil(log2(2m-1)) = m+n bits.
NOTE for the TAs: The objective of this question is to promote analytical skills by forcing
students to evaluate how unsigned notation will work for arbitrary length numbers.

Ans 8 :
Way 1: We can throw an exception whenever an overflow occurs. This will force the
programmer to write code that explicitly defines what to do in case of overflows.
Way 2: Another alternative is to define an ISA whose semantics are invariant of the size of a
number. As a result, the ISA is expected to handle numbers of arbitrary length correctly. One way
to do this might be storing a number initially using x bits. Whenever an overflow occurs, x is
incremented, and the operation which caused the overflow is re-executed. This incrementing of x
is done until no overflow occurs.
Use 1: If the programmer wants to write code for a critical application, then he/she might not
want unexpected and unhandled overflows. In such cases, unexpected and unhandled
overflows might result in an undefined state, which might be dangerous.
Use 2: Suppose the programmer works with very large numbers and is worried about the
memory footprint of the application. If a number is small, then it does not make sense to waste
redundant bits for its representation, just to support larger numbers. The Way 2 described above
can be used to handle such scenarios. In such microarchitectures, larger numbers are given more
bits and smaller numbers less bits, resulting in a more optimal memory usage.
NOTE for the TAs: There is no fixed answer for this question. The objective of this question is to
promote problem solving skills.

Ans 9:
Add r3, r1, r2
Sub r3, r3, r4
Sub r3, r3, r7
Add r2, r3, r3
Sub r2, r2, r1
Sub r2, r2, r1