# Ćwiczenia 2, grupa cz. 12-14, 17. marca 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Daniel Boguszewski | X | X | X | X | X | | X | X | |
Adam Ciężkowski | | | | | | | | | |
Jacek Długopolski | X | X | X | X | ==X== | X | X | X | |
Jakub Fila | X | X | X | X | | | X | X | |
Krzysztof Grynkiewicz | | | | | | | | | |
Michał Hetnar | x | x | x | x | x | x | x | x | |
Hubert Jabłoński | x | x | x | x | | x | x | | |
Antoni Kamiński | X | X | X | | X | | X | | |
Paweł Karaś | X | X | X | X | X | | X | X | |
Emil Kisielewicz | | | | | | | | | |
Kacper Komenda | X | X | | | | | X | | |
Filip Komorowski | x | ==x== | x | x | x | x | x | | |
Piotr Piesiak | x | x |==x==| x |x | x | x | x | |
Artur Krzyżyński | x | x | x | x | x | x | x | | |
Patryk Mazur |==X== | X | X | X | X | | X | | |
Szymon Mleczko | X | X | X | X | X | X | X | | |
Michał Mróz | X | X | X | X | X | | | | |
Dominik Olejarz | | | | | | | | | |
Magdalena Słonińska | X | X | X | X | | | X | | |
Joanna Stachowicz | | | | | | | | | |
Adam Szeruda | X | X | X | X | X | X | X | X | |
Kamil Tasarz | X | X | X | | X | | X | X | |
Michał Zieliński | X | X | X | X | | X | ==X== | X | |
:::

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

## Zadanie 1

:::success
Autor: Michał Hetnar
:::

(i) Jeśli najmniej znaczący bit A wynosi 1, to rejestr B, zawierający b, jest
dodane do P; w przeciwnym razie 0 jest dodawane do P. Suma jest umieszczana w P.

(ii) Rejestry P i A są przesunięte w prawo, z wykonaniem przesuniętej sumy
do bitu wyższego rzędu P, bit niższego rzędu P jest przeniesiony do rejestru A,
a skrajny prawy bit A, który nie jest używany w pozostałej części algorytmu, to
przesunięty

A = 3
B = 9
1001
P____A
0000 .0011
| (i) +B
v
P____A
1001 .0011
| (ii) ->
V

P____A
0100 1.001
| (i) +B
v
P____A
1101 1.001
| (ii) ->
V

P____A
0110 11.00
| (i) +0
v
P____A
0110 11.00
| (ii) ->
V

P____A
0011 011.0
| (i) +0
v
P____A
0011 011.0
| (ii) ->
V

P____A
0001 1011.
| (i) +0
v
P____A
0001 1011.
| (ii) ->
V
1+2+8+16 =27
:::

## Zadanie 2

:::success
Autor: Filip Komorowski
:::


Shift -> Arithmetic shift


## Zadanie 3

:::success
Autor: Jakub Fila
:::


## Zadanie 4

:::success
Autor: Paweł Karaś
:::


## Zadanie 5

:::success
Autor: Piotr Piesiak
:::
Idea:
wykorzystujemy pomysł z zadania 4 z kodowaniem Bootha
Powyższe zasady mówią nam kiedy należy dodać/odjąć B
Struktura tego algorytmu byłaby analogiczna do struktury z zadania 5
Mnożenie liczb A=-9,B=-3:

## Zadanie 6

:::success
Autor: Hubert Jabłoński
:::



## Zadanie 7

:::success
Autor: Michał Zieliński
:::

### Treść
Przedstaw zasadę działania układu dzielącego dwie liczby bez znaku w wersji restoring division. Wykonaj dzielenie za pomocą tego układu liczb 4-bitowych A = 9 przez B = 3.

### Rozwiązanie

#### Algorytm
Mamy rejestry A, B, P. W A mamy liczbę dzieloną, w B li
dla liczb n bitowych n razy robimy:
1. (P,A) przesuwamy w lewo
2. w P zapisujemy P-B
3. "najbardziej prawy" bit A przyjmuje 0 gdy P<0, 1 wpp
4. jeżeli P jest ujemne zapisujemy tam P+B
W A mamy część całkowitą dzielenia, w P resztę
#### Obliczenia dla A = 9, B = 3
1. P=0000 A=1001 b=0011
2. przesun P=0001 A=001x
3. mamy ujemne wiec A=0010
4. przesun P=0010 A=010x
5. ujemne wiec A=0100
6. przesun P=0100 A=100x
7. dodatnie wiec P=0001 A=1001
8. przesun P=0011 A=001x
9. dodatnie wiec P=0000 A=0011

## Zadanie 8

:::success
Autor: Adam Szeruda
:::

* jeżeli $P < 0$:
* przesuń $(P, A)$ w lewo
* zapisz w $P$ wynik $P+B$
* w przeciwnym razie:
* przesuń $(P, A)$ w lewo
* zapisz w $P$ wynik $P-B$
* jeżeli $P \geq 0$, ustaw ostatni bit $A$ na 1

 A =   1001
 B = 0 0011
-B = 1 1101

s    P    A
0 0000 1001   <<
0 0001 0010   -B
1 1110 0010   ustaw bit na 0

1 1110 0010   <<
1 1100 0100   +B
1 1111 0100   ustaw bit na 0

1 1111 0100   <<
1 1110 1000   +B
0 0001 1000   ustaw bit na 1

0 0001 1001   <<
0 0011 0010   -B
0 0000 0010   ustaw bit na 1

0 0000 0011

Dowód poprawności - wykonujemy jednocześnie dzielenie metodą restoring i nonrestoring.

$P$ - rejestr restoring, $P'$ - rejestr nonrestoring

* krok (a), $P = P' \geq 0$:
* $P \leftarrow 2P$, $P' \leftarrow 2P'$
* $P \leftarrow P - B$, $P' \leftarrow P' - B$
* jeżeli $P \geq 0$:
* ustaw ostatni bit $A$ na $1$
* przejdź do kroku (a)
* w przeciwnym razie:
* $P \leftarrow P + B$
* przejdź do kroku (b)
* krok (b), $P' = P - B < 0$:
* $P \leftarrow 2P$, $P' \leftarrow 2P'$
* $P \leftarrow P - B$, $P' \leftarrow P' + B$
* w tym miejscu $P = P'$
* jeżeli $P \geq 0$:
* ustaw ostatni bit $A$ na $1$
* przejdź do kroku (a)
* w przeciwnym razie:
* $P \leftarrow P + B$
* przejdź do kroku (b)

Zawartość rejestru $A$ jest modyfikowana w ten sam sposób przez obie metody, więc skoro metoda restoring zwraca poprawny wynik, to nonrestoring również.

## Zadanie 9

:::danger
Autor: do-deklarować
:::