CS1200 Assignment 1 Solved

QUESTION 1. COMPLEMENT NUMBER SYSTEMS (10 MARKS)
In the lectures we saw the 2’s complement and 1’s complement number system which are based on the binary (base 2) system. Here we will explore other complement number systems under other bases.

a. Given a base B (≥ 2), derive a formula to calculate X’, the n-digit B’s complement of a number X.   (1 mark) b. An additive inverse of a number a is a number b such that a + b = 0. Prove that the B’s complement, n’, of a number n, is the additive inverse of n.      

c.       Find the four digit 10’s complement representation of the decimal numbers 123  and -456. I.e. you should find the representation of the two numbers in 10’s complement and not their negation.   

 

d.      Following the procedure for subtraction of two 2’s complement numbers in base 2 (by converting it into an addition operation like what you did in tutorial 1), compute the following subtraction in 4-digit 10’s complement. Show your working and give your final answer in 10’s complement.  

123 – 456

             

 

QUESTION 2. FLOATING POINT NUMBERS (12 MARKS)
 

a.      When representing n-bit signed numbers in excess notation, briefly explain, using a 3bit signed number system as example, why the excess chosen is usually 2n-1. 

 

In the following parts we will use an 8-bit floating point representation with this format:

 

Sign
Exponent
Mantissa
1-bit
3-bit excess-4
5 bits normalized with 1 hidden bit (i.e. only 4 bits of the mantissa are stored)
 

b.      What are the smallest and largest positive decimal numbers that can be represented? We assume that the entire range of exponent values can be used, i.e. there are no exponent values with special meanings. Write your answers in decimal.  

 

c.       Find the normalized representation for these two numbers in the 8-bit floating point representation above. You should calculate the mantissa to one bit more than you require and round up the result if necessary. Write your answer in hexadecimal.  


X  = 4.4  

Y  = –0.7   

 

d.      Are the two numbers represented perfectly in this floating-point representation? If no, what is the error in the representation for each number (i.e. the difference between the actual value and the floating point representation)? 

 

e.      Is the accuracy of one of the two numbers better than the other? Explain.             (1 mark) QUESTION 3. STRUCTURES IN C 

In this question we will examine how C stores structures in memory.  

a.      Compile and run the enclosed q3.c program using gcc on PC, MacOS or Sunfire. The code included is at the end of this file for your reference. Complete the following tables:       

 

Table 1: Component Sizes

Variable
Size in bytes
t1.num1
 
t1.ch
 
t1.num2
 
 

Table 2: Component Addresses

Variable
Address
&t1.num1
 
&t1.ch
 
&t1.num2
 
 

Table 3: Array Element Addresses

Variable
Address
&t2[0]
 
&t2[1]
 
&t2[2]
 
 

b.      Look at the addresses of t1.ch and t1.num2 in Table 2. Do they differ by 1 byte or 4 bytes? Explain why, with reference to the size of t1.ch.  (1 mark)

 

c.       The code fragment from q3.c sums the num2 component of the array t2 and stores the total in result.num2.  

… <other code here> … 

 

mystruct_t result = {0.0, ' ', 0}; int i; 

 

… <other code here> … 

 

for (i=0; i<6; i++) { 

 result.num2 = result.num2 + t2[i].num2; } 
 

Assuming that $s0 contains the base address of t2, $s1 contains the address of result and $t0 is mapped to the variable i, rewrite the for-loop part of the code in MIPS assembly. Ensure that your code is properly commented or marks will be deducted. Note also that pseudoinstructions other than those required for any unaligned loads and stores are not allowed. (Hint: Look at Table 3 to see how far apart each element of t2 is in memory).  (4 marks) QUESTION 4. ANALYSIS OF MIPS ASSEMBLY PROGRAM (7 MARKS) 

 

Line 
Labels 
Instructions 
1
 
addi $1, $0, 0 
2
 
add  $3, $20, $1 
3
loop: 
lw   $4, 0($3) 
4
 
srl  $5, $4, 16 
5
 
sll  $6, $4, 16 
6
 
or   $4, $5, $6 
7
 
sw   $4, 0($3) 
8
 
addi $1, $1, 1 
9
 
slt  $5, $1, $21 
10
 
beq  $5, $zero, loop 
 

The program above goes through the elements of an integer array whose base address is in register $20, and the number of elements is in register $21. It does something with the data in the array and writes it back.

a.      Unfortunately, this program does not work as intended. Rewrite the program so that it works properly, changing only what is necessary. You may also add instructions but these should be kept to the absolute minimum. You may assume that there are no errors in lines 4 to 6 inclusive and you are NOT allowed to change these lines.   

                                                                                                                                           (3 marks)

 

b.      How many instructions are executed in the CORRECTED program if $21 = 5? (2 marks)

 

c.       Describe in one sentence what the CORRECTED program does.             (2 marks) Code for q3.c 

 

This is provided only for your reference.  You do not need to type it in.

 

#include <stdio.h> 

 

typedef struct {     float num1;     char ch;     int num2; } mystruct_t; 

 

int main() { 

 

    mystruct_t t1, t2[6]; 

    mystruct_t result = {0.0, ' ', 0};     int i; 

 

    printf("Structure component sizes:\n"); 

    printf("Size of t1.num1 = %lu bytes.\n", sizeof(t1.num1));     printf("Size of t1.ch = %lu bytes.\n", sizeof(t1.ch));     printf("Size of t1.num2 = %lu bytes.\n\n", sizeof(t1.num2)); 

 

    printf("Structure component addresses:\n");     printf("Address of t1.num1 = %p.\n", &t1.num1);     printf("Address of t1.ch = %p.\n", &t1.ch);     printf("Address of t1.num2 = %p.\n\n", &t1.num2); 

 

    printf("Array element addresses:\n");     printf("Address of t2[0] = %p.\n", t2);     printf("Address of t2[1] = %p.\n", &t2[1]);     printf("Address of t2[2] = %p.\n", &t2[2]); 

 

    for (i=0; i<6; i++) 

        result.num2 = result.num2 + t2[i].num2; 

 

    return 0; 

}