Програмирање 2/К1П 2019

Popravni prvi kolokvijum 2019. godine održan je 22. aprila. Zadaci i rešenja dostupni su sa stranice predmeta.

Pitanja

1. pitanje

Na nekom računaru, realni brojevi se predstavljaju na širini od 10 bita u formatu seeeemmmmm, gde je s predznak broja, eeee su bitovi eksponenta u kodu sa viškom 7 i mmmmm su biti normalizovane mantise sa skrivenim bitom (1≤M<2). Celi brojevi se predstavljaju na širini od 8 bita u komplementu dvojke. Neka se u celobrojnoj lokaciji A nalazi broj čija je predstava 82₁₆, dok se u realnoj lokaciji B nalazi broj čija je vrednost 13.25₁₀. Kako na datom računaru izgleda predstava broja koji je rezultat operacije A + B? Sva zaokruživanja se obavljaju prema pravilima ANSI/IEEE standarda za realne brojeve.

Postavka

Treba sabrati dva realna broja. Za početak pretvorimo ono što nam je dato u realne brojeve po formatu.

• Broj biti eksponenta je k = 4
• Višak (IEEE) je v = 2^4-1-1 = 7
• Broj biti mantise je p = 5
• Mantisa je IEEE formata 1.xxxxx

Broj A

8 bita, komplement 2, dakle poslednji bit određuje znak. A = 82₁₆ = 1000 0010. Broj je očigledno negativan. Komplementiramo da izvučemo vrednost. A = - 111 1110 = -126.

Treba normalizovati ovaj broj da bi stao u format mantise. 111 1110 => 1.11 1110. Pomeranjem ulevo za 6 mesta dobijamo broj A_f = - 1.111110 * 2⁶. Eksponent E = 6. Podvlačimo mantisu: M_A = 11111. Ovde nije bilo zaokruživanja (pravilo 1). Tako da je broj u zapisu -1.11111 * 2⁶.

Broj B

B = 13.25. Pretvaramo odvojeno celi i decimalni deo. 13₁₀ = 1101₂ 0.25₁₀ = 0.01₂ Spojimo i dobijemo 1101.01. Normalizujemo tako da stane u format mantise pomeranjem zareza ulevo. 1.10101 * 2³. Eksponent je E = 3. Broj B_f = 1.10101 * 2³.

Sabiranje

Broj B se dovodi na veći eksponent, pri tome se zaokružuje mantisa (pravilo 2). B_f = 1.10101 * 2³ = 0.00110101 * 2⁶ = 0.00111 * 2⁶.

Očekujemo negativan broj jer je |A|>|B|. Oduzimamo realne binarne brojeve: A_f + B_f = 0.00111 * 2 ⁶ - 1.11111 * 2⁶ = -(1.11111 * 2⁶ - 0.00111 * 2 ⁶) = - 1.11000 * 2⁶.

Reprezentacija

Naš broj je - 1.11000 * 2⁶. Konvertujemo ga u predstavu formata:

s eeee mmmmm

Znak je - pa je bit s 1.

1 eeee mmmmm

Eksponentu dodajemo pomeraj (višak). e = E + v = 6 + 7 = 13 = 1101₂.

1 1101 mmmmm

Mantisu prepišemo

1 1101 11000

Pretvorimo u hex broj:

0011 1011 1000 = 3B8.

2. pitanje

Na nekom računaru, realni brojevi se predstavljaju na širini od 10 bita u formatu seeeemmmmm, gde je s bit predviđen za kodiranje predznaka broja, eeee su 4 bitova za eksponent u kodu sa viškom 7, a mmmmm su biti normalizovane matise sa skrivenim bitom (1≤M<2). Na ovom računaru se učitavaju dva cela broja koji se smešaju u realne lokacije i čije su vrednosti 240 i 13. Potom se isti brojevi saberu i rezultat upiše u treću realnu lokaciju. Koja je apsolutna vrednost razlike dobijenog rezultata i potpuno tačnog zbira unetih brojeva? Sva zaokruživanja se obavljaju prema pravilima ANSI/IEEE standarda za realne brojeve.

Postavka

• w = 10
• k = 4, v = 7 (IEEE)
• p = 5
• IEEE format mantise 1.xxxxxx

Treba sabrati realne brojeve A i B, traži se greška tj apsolutna vrednost razlike dobijenog rezultata i potpuno tačnog zbira. Potpuno tačan zbir Z = A + B = 240 + 13 = 253.

Broj A

A = 240₁₀.

Pretvorimo u binarni broj: A = 1111 0000 * 2⁰. Treba normalizovati mantisu, pa zaokružiti na broj bitova.

A = 1111 0000 * 2⁰ = 1.1110000 * 2⁷. (Pravilo 1)

A_f = 1.11100 * 2⁷.

Broj B

B = 13₁₀

Primeniti isti postupak. B = 13₁₀ = 1101₂ * 2⁰.

Normalizacija: B = 1.101 * 2³

Neophodno je dovesti na isti eksponent radi sabiranja pomeranjem ulevo za 4:

B = 0.0001101 * 2⁷.

B = 0.00011 01 * 2⁷.

B_f = 0.00011 * 2⁷.

Sabiranje

S = A_f + B_f = 1.11100 * 2⁷ + 0.00011 * 2⁷ = 1.11111 * 2⁷.

S = 1.11111 * 2⁷ = 1111 1100 = 240 + 12 = 252.

R = |S-Z| = |252-253| = 1. (B)

3. pitanje

#include <stdio.h> 
int main(void) {    
   int nums[] = { 0x21, -3, 011, 5, 04, 0 }, s = 0;
   // Niz će imati vrednosti 33, -3, 9, 5, 4, 0.

   // Uslov se računa kao veličina niza kroz veličina jednog člana, što daje broj članova, ali jedan manje jer se u foru gleda sledeći član. 
   for(int i=0; i<sizeof(nums)/sizeof(int)-1; i++) { 
     // Prvi i sledeći član.
     int x = nums[i], y = nums[i+1];
     
     int mask = x >> sizeof(int)*8 - 1;
     // * i - ima prednost u odnosu na >>. Uzmimo da je int veličine 4.
     // mask = x >> 4*8 - 1 
     // mask = x >> 31
     // Očigledno je da se ovde pomera 31 bit da bi na najnižem dobili bit za znak.
     // Stvar je u tome što za negativne brojeve, pomeranje udesno za negativne brojeve sa desne strane uvodi 1 a ne 0 da bi se zadržao znak.
     // Npr 0x21 >> 31 = 0b00000000
     // Ali -3 = 1111 .... 1101 >> 31 = 1111 .... 1111 tj maska sa sve 1.

     x = (x + mask) ^ mask;
     // Ovde pozitivni brojevi ostaju nepromenjeni, a negativnima se dodaje maska pa okreće svaki bit. U prevodu - okreće im se znak komplementiranjem i postaju pozitivni.
     while(y > 0) { 
        // Ako je član desno od trenutnog paran, dodaj na sumu x.
        if(y&1) s += x;
         // Množimo trenutni sa 2
         x <<= 1;
         // Delimo naredni sa 2. Uslov whilea je da se ponavlja dok y ne postane 0. 
         y >>= 1;
      }
   // Ovo je egipćanski algoritam za množenje dva broja star hiljadama godina, množi dva susedna broja i dodaje ih na sumu. Još jedan dokaz da je Milo zapravo faraon.
   }
   printf("%d", s);
}

4. pitanje

Ova pitalica se reši na pogled. Jedino treba proveriti da li je (B) ili nijedan od ponuđenih odgovora. Funkcija printf nikad neće vratiti string ako joj je dat formatski specifikator %d. Nazivi enumova postoje samo u kodu i gube se tokom kompilacije, tako da je jedino smisleno rešenje (B) 3 91.