Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica

Home | Avvisi | Diario Lezioni | Esercitazioni | Esami | Materiale Didattico | Valutazioni Studenti | Lezioni di Camil Demetrescu |

[T06] Esercitazione 6

Istruzioni per l’esercitazione:

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (Ricerca binaria in un array ordinato)

Tradurre nel file E1/e1.s la seguente funzione C contenuta in E1/e1.c che implementa il classico algoritmo ricerca binaria (o dicotomica) restituento 1 se x appartiene all’array v di n interi int e 0 altrimenti. Usare il file E1/e1_eq.c per sviluppare la versione C equivalente.

#include "e1.h"

int binsearch(int *v, int n, int x) {
    int i=0, j=n;
    while (i<j) {
        int m = (i+j)/2;
        if (v[m]==x) return 1;
        if (v[m]>x) j=m;
        else i=m+1;
    }
    return 0;
}

Suggerimento: usare lo shift per dividere per 2.

Usare il main di prova nella directory di lavoro E1 compilando con gcc -m32 e1_main.c e1.s -o e1.

Esercizio 2 (Minimo Comune Multiplo)

Tradurre nel file E2/e2.s la seguente funzione C contenuta in E2/e2.c che, dati due interi, ne calcola il minimi comune multiplo. Usare il file E2/e2_eq.c per sviluppare la versione C equivalente.

#include "e2.h"

int lcm(int x, int y) {
    int greater = y;
    if (x > y)
        greater = x;
    while (1) {
        if ((greater % x == 0) && (greater % y == 0))
            return greater;
        greater++;
    }
}

Suggerimento: usare le istruzioni CMOVcc e SETcc.

Usare il main di prova nella directory di lavoro E2 compilando con gcc -m32 e2_main.c e2.s -o e2.

Esercizio 3 (Frequenza caratteri)

Tradurre nel file E3/e3.s la seguente funzione C contenuta in E3/e3.c che, data una stringa C, calcola la frequenza dei caratteri nel testo e restituisce il carattere ASCII più frequente. Usare il file E3/e3_eq.c per sviluppare la versione C equivalente.

#include <string.h>
#include "e3.h"

char charfreq(const char* s) {
    unsigned freq[256];
    memset(freq, 0, 256*sizeof(unsigned));

    while (*s) freq[*s++]++;

    unsigned maxi = 0;
    unsigned maxf = freq[0];
    int i;
    for (i=1; i<256; ++i){
        if (freq[i]>maxf) {
            maxi = i;        // A1
            maxf = freq[i];  // A2
        }
    }
    return maxi;
}

Suggerimento: usare l’istruzione CMOVcc per fare i due assegnamenti condizionali A1 e A2.

Usare il main di prova nella directory di lavoro E3 compilando con gcc -m32 e3_main.c e3.s -o e3.

Esercizio 4 (Domande)

Rispondi alle seguenti domande, tenendo conto che una risposta corretta vale 1 punti, mentre una risposta errata vale 0 punti.

Domanda 1. Siano %eax=20 (decimale), %edx=0 (decimale) e %ecx=8 (decimale). Con riguardo alle due istruzioni “idivl %ecx” e “sarl $3, %eax”, quale delle seguenti affermazioni risulta vera:

Domanda 2. Assumendo %eax=0xFF000000, %ecx=1 (decimale) e %edx=10 (decimale), dopo aver eseguito l’istruzione “testl %eax, %eax” quale delle seguenti affermazioni risulta vera:

Domanda 3. Assumendo %eax=10 (decimale), %ecx=7 (decimale) e %edx=2 (decimale), quale delle seguenti affermazioni risulta vera:

Domanda 4. Quale delle seguenti è un’istruzione valida: