# Ćwiczenia 2, grupa śr. 10-12, 8 marca 2023

###### tags: `SYK23` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mateusz Biłyk | X | X | X | X | X | X | X | X | X |
Mikołaj Dworszczak | | | | | | | | | |
Kacper Jóźwiak |==X== | X | X | X | X | | X | | |
Dominik Kiełbowicz | | | | | | | | | |
Michał Kolasa | | | | | | | | | |
Konrad Kowalczyk | X | X | X | | | | X | | |
Oskar Kropielnicki | X | X | X | | | | X | X | |
Anna Krysta | X | X | X | X | X | X | X | X | |
Jakub Krzyżowski | X | X | X | X | X | | X | | |
Oskar Kubkowski | X | X | X | X | X | | | | |
Patryk Maciąg | | | | | | | | | |
Mateusz Mazur | X | X | ==X== | X | X | | X | X | |
Barbara Moczulska | X | X | X | | | | | | |
Kacper Sojda | | | | | | | | | |
Marta Strzelec | X | X | X | X |X| | | | |
Mikołaj Swoboda | | | | | | | | | |
Filip Szczepański | x | ==x== | x | x | x | | | | |
Julian Włodarek | ==x== | x | x | x | x | | | | |
Beata Łakoma | x | x | x | x | x | x | x | x | |
Michał Łukasik | X | X | X | | | | X | X | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Julian Włodarek
:::


A=9=1001, B=3=0011, P=0000
1. 0000 1001 start
2. 0011 1001 +B
3. 0001 1100 >>
4. 0001 1100 +0
5. 0000 1110 >>
6. 0000 1110 +0
7. 0000 0111 >>
8. 0011 0111 +B
9. 0001 1011 >>
Wynik: 0001 1011 = 27

## Zadanie 2
:::success
Autor: Filip Szczepański
:::

A = 1001
B = 1101
P = 0000
P A
0000 1001 - start
1101 1001 - +B
1110 1100 - shift
1110 1100 - +0
1111 0110 - shift
1111 0110 - +0
1111 1011 - shift
1100 1011 - +B
1110 0101 - shift
wynik = 1110 0101 = -27

## Zadanie 3
:::success
Autor: Mateusz Mazur
:::

**Pomysł**

**Algorytm**
1. Jeśli najmniej znaczący bit A wynosi 1 to $P = P + B$ (w p.p. pomiń ten krok).
2. Przesuń P, A w prawo.
3. Przenieś carry-out do najwyższego bitu P, a najmniejszy bit P przenieś do skrajnego prawego bitu A.

**przykład**
$9*3$

| | start | 1. | 2. | 3. | 2. | 3. | 1. | 2. | 3. |
| - | ----- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ----- |
| A | 1001 | 1001 | 0100 | 1100 | 0110 | 1011 | 1011 | 0101 | 1010 |
| B | 0011 | 0011 | 0011 | 0011 | 0011 | 0011 | 0011 | 0011 | 0011 |
| P | 0000 | 0011 | 0001 | 0001 | 0000 | 0000 | 0011 | 0001 | 0001 |
| $c_{out}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

$9*3 = PA = 0001\space0101 = 27$

## Zadanie 4
:::success
Autor: Jakub Krzyżowski
:::
Kodowanie Bootha polega na rekodowaniu liczb jako różnica innych liczb np.
7 = 8 - 1 = 1000 - 0001, albo
-4 = 1100 pomyślimy o tym jako o liczbie bez znaku,
czyli 1100 = 12 = 16 - 4 = 10000 - 0100
Mnożenie A = -9 = 10111, B = 3 = 00011, -B = 11101
Start P = 00000, A = 10111
1. a) suma: P = 11101, A = 10111 L = 0
b) shift: P = 11110, A = 11011 L = 1
2. a) suma z 0
b) shift: P = 11111, A = 01101 L = 1
3. a) suma z 0
b) shift: P = 11111, A = 10110 L = 1
4. a) suma: P = 00010, A = 10110 L = 1
b) shift: P = 00001, A = 01011 L = 0
5. a) suma: P = 11110, A = 01011 L = 0
b) shift: P = 11111, A = 00101

Wynik = 1111100101 = -27

## Zadanie 5
:::success
Autor: Mateusz Biłyk
:::
Łączymy pomysły z zadań 2- odpowiednie przesuwanie rejestru P oraz pomysł z zadania 4 związany z kodowanie Bootha, aby stworzyć algorytm, kóry jest w stanie pomnożyć liczby dowolnych znaków. Struktura i algorytm jest taki jak w poprzednich zadaniach.
|n| A | B | P |
|-|-----|-----|-----|
|1|10111|11101|00000|
|2|11011|11101|00001|
|3|11101|11101|00000|
|4|01110|11101|00000|
|5|10111|11101|11110|
|6|11011|11101|00000|

$11011_2=27$

## Zadanie 6
:::success
Autor: Anna Krysta
:::

## Zadanie 7
:::success
Autor: Beata Łakoma
:::

Przykład:
a=1111=15 b=0011=3

p a
0000 1111
0001 111x (i)
neg 111x (ii)
neg 1110 (iii)
0001 1110 (iv)
0011 110x (i)
0000 110x (ii)
0000 1101 (iii)
0001 101x (i)
neg 101x (ii)
neg 1010 (iii)
0001 1010 (iv)
0011 010x (i)
0000 010x (ii)
0000 0101 (iii)

wynik 0101= 5

## Zadanie 8
:::success
Autor: Michał Łukasik
:::

Sposób działania:
1. W rejestrze P umieszczamy zera, w rejestrze A liczbę a, w rejestrze B liczbę b
2. Wykonujemy n razy (gdzie n oznacza ilu bitowe są liczby):
* Bity w rejestrach P i A przesuwamy w lewo
* Jeśli liczba w P jest ujemna:
Do rejestru P dodajemy wartość rejestru B
* W przeciwnym przypadku:
Od rejestru P odejmujemy wartość rejestru B
* Jeśli wynik jest ujemny:
najmniej znaczący bit A ustawiamy na 0
* w przeciwnym wypadku
najmniej znaczący bit A ustawiamy na 1
3. W rejestrze A jest wynik dzielenia, w rejestrze P jest reszta

Zauważmy, że działanie tego algorytmu jest podobne do działania algorytmu restoring division.
Gdy P jest dodatnie, algorytm działa tak samo jak restoring division.
Gdy P jest ujemne, to nie wykonujemy restore w rejestrze P, więc
wartość w rejestrze P jest mniejsza o B niż w sytuacji gdybyśmy zrobili restore.
Następnie po przesunięciu w lewo P w następnym kroku wartość w P jest mniejsza o 2B niż gdybyśmy zrobili restore, ale skoro P jest ujemne to ten algorytm doda B do P
stąd otrzymamy odpowiednią wartość P, tak jak w algorytmie restoring division.

dzielenie 10/3

0000 | 1010
przesunięcie
0001 | 010? odejmowanie
1110 | 0100
przesunięcie
1100 | 100? dodawanie
1111 | 1000
przesunięcie
1111 | 000? dodawanie
0010 | 0001
przesunięcie
0100 | 001? odejmowanie
0001 | 0011

reszta 1, wynik 3

## Zadanie 9
:::success
Autor: Mateusz Biłyk
:::
#### Sposób działania algorytmu:

#### Przykład:

#### Wytłumaczenie
Algroytm ten działa trochę w inny sposób od innych algorytmów dzielenia. On ma za zadanie wyprodukować dwie liczby, po których odjęciu dostaniemy żądany wynik. Trzon pomysłu tego alogrytmu dalej jednak bazuje na dzieleniu pisemnym. Po piewsze myślimy o liczbach w rejestrach A oraz B jakby były to liczby z przecinkiem przed najstarszym bitem, czyli w naszym przypadku $1000_2/0011_2=0.1000_2/0.0011_2$. Parę rejestrów $(P,A)$ trzyma resztę z dzielenia traktowaną na przykład jeżeli rejestr P ma $11110_2$ a rejest A=0 to traktujemy to jako $r=1.1110_2=-1/8$. Algorytm najpierw przesuwa wszystkie rejestry o tyle bitów aby $b\geq 1/2$.Teraz mamy trzy opcję: a) $-1/4\leq r < 1/4$ reszta jest za mała, patrząc na wartość bezwzględną, aby co kolwiek do niej dodać lub odjąć, wiec dajemy zero i mnożymy resztę przez 2, b) $r<-1/4$ reszta jest mała i musimy po pomnożeniu przez dwa dodać b i ustawić -1 w bitach wynikowych c) $r \geq 1/4$ reszta robi się za duża więc musimy pomnożyć r przez 2, odjąć b , ustawić 1 w wyniku. Taką procedurą na tej samej zasadzie jaką działa algorytm dzielenia pisemnego (dobieranie największych liczb, które się mieszczą w naszej liczbie), otrzymujemy wynik. Po tej procedurze zostanie nam reszta $<1$ oraz dwie liczby, które po dodaniu dają nam wynik. Algorytm ten jest szybki w przypadku, gdy dane dobrane są tak, że w wyniku dużo bitów to zera, wtedy nie trzeba dodawać ani odejmować b w naszej procedurze.

B*k + l