Zadanie 1.2, matura czerwiec 2015, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. Kod uzupełnień do dwóch
W kodzie uzupełnień do dwóch (w skrócie U2) zapisujemy liczby całkowite w dwójkowym systemie pozycyjnym. W n-bitowym systemie U2 reprezentujemy liczby całkowite z przedziału [−(2n−1), 2n−1 − 1]. Przykładowo – dla n = 8 są to liczby:
–128, –127, ..., 0, 1, ..., 127.
Zapis (an−1an−2…a2a1a0)U2, gdzie , oznacza liczbę
−an−1 ⋅ 2n−1 + an−2 ⋅ 2n−2 + ⋯ + a1 ⋅ 21 + a0 ⋅ 20.
W porównaniu do klasycznego zapisu dwójkowego, w kodzie U2 najbardziej znaczący bit (an−1) ma przeciwną „wagę”. Przykładowo: w reprezentacji 8-bitowej (n = 8) wagi bitów a0, a1, a2, a3, a4, a5, a6, a7 są równe odpowiednio: 1, 2, 4, 8, ..., 64, –128. W takim systemie reprezentacje liczb 117 i –82 wyglądają następująco:
(01110101)U2 = −0 ⋅ 27 + 1 ⋅ 26 + 1 ⋅ 25 + 1 ⋅ 24 + 0 ⋅ 23 + 1 ⋅ 22 + 0 ⋅ 21 + 1 ⋅ 20 =
= 64 + 32 + 16 + 4 + 1 = 117
(10101110)U2 = −1 ⋅ 27 + 0 ⋅ 26 + 1 ⋅ 25 + 0 ⋅ 24 + 1 ⋅ 23 + 1 ⋅ 22 + 1 ⋅ 21 + 0 ⋅ 20 =
= −128 + 32 + 8 + 4 + 2 = −82
Polecenie
3 punktyPoniżej przedstawiono algorytm wyznaczania liczby przeciwnej do danej liczby zapisanej w kodzie U2.
Specyfikacja:
Dane: liczba naturalna n > 1, reprezentacja (an−1an−2…a2a1a0)U2 liczby naturalnej x (x ≠ 0 oraz x ≠ −2n−1) w n-bitowym kodzie U2.
Wynik: reprezentacja (bn−1bn−2…b2b1b0)U2 liczby (–x) w n-bitowym kodzie U2.
Algorytm:
```text
1. i ← 0
2. dopóki a_i = 0 wykonuj:
a) b_i ← 0
b) i ← i + 1
3. b_i ← a_i
4. i ← i + 1
5. dopóki i < n wykonuj:
a) b_i ← not(a_i)
b) i ← i + 1
```
Uwaga: not oznacza negację bitu, tzn. not(0) = 1, not(1) = 0.
Podaj wynik wykonania algorytmu dla n = 16 i x = (1111001001110000)U2
Podaj przykład liczby zapisanej w 16-bitowym kodzie U2, dla której algorytm nie wykona żadnej instrukcji z wnętrza pętli w kroku 2.
Podaj przykład liczby zapisanej w 16-bitowym kodzie U2, dla której algorytm w pętli z kroku 5 wykona dokładnie 7 razy operację not.
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
1. (0000110110010000)U2; i = 4, ai = 1
2. Dowolny ciąg zerojedynkowy o długości 16, zakończony jedynką, tzn. ciąg postaci xxxxxxxxxxxxxxx1.
3. Dowolny ciąg zerojedynkowy o długości 16, którego 9 ostatnich bitów to 100000000, tzn. ciąg postaci: xxxxxxx100000000
Schemat punktowania
poprawny wynik algorytmu oraz poprawny bit ai oraz indeks.
poprawny przykład liczby dla której algorytm nie wykona instrukcji w kroku 2.
poprawny przykład liczby dla której operacja not w kroku 5 wykona się dokładnie 7 razy.