---
# System prepended metadata

title: 'Ćwiczenia 2, grupa cz. 14-16, 9 marca 2023'
tags: [pwit, ćwiczenia, SYK23]

---

# Ćwiczenia 2, grupa cz. 14-16, 9 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   |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki         |       |     |     |     |     |     |     |     |     |
Wojciech Bogucki         |   X   |  X  |  X  |  X  |  X  |     |  X  |  X  |     |
Mateusz Cerulewicz       |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Mateusz Garncarczyk      |   X   |  X  |  X  |  X  |  X  |     |  X  |  X  |     |
Mateusz Golisz           |       |     |     |     |     |     |     |     |     |
Mateusz Kitzol           |   X   |  X  |  X  |  X  |  X  |     |     |     |     |
Piotr Mańkowski          |       |     |     |     |     |     |     |     |     |
Michał Mękarski          |       |     |     |     |     |     |     |     |     |
Aleksandra Nicpoń        |   X   | ==X== |  X   | X    |  X   |   |   X  |  X   |     |
Ksawery Plis             |   X   |  X  |  ==X==   |  X   |   X  |     |   X  |    X |     |
Patryk Rybak             |       |     |     |     |     |     |     |     |     |
Rafał Spyra              | ==X== |  X  |  X  |  X  |  X  |     |     |     |     |
Dominik Szczepaniak      |   X   |  X  |  X  |  X  |  X  |     |  ==X==  |  X  |     |
Taras Tsehenko           |       |     |     |     |     |     |     |     |     |
Maksymilian Wiśniewski   |       |     |     |     |     |     |     |     |     |
Martyna Wybraniec        |   X   |  X  |  X  |  X  |  X  |     |  X  |  X  |     |
Natalia Zychowicz        |   X   |  X  |  X  |   X |   ==X== |     |   X |   X |     |
Patryk Maciąg |X|X|X||||X|X||
:::

W tym miejscu można zadeklarować zad. **6** i **8** z **listy 1**:

|Imię i nazwisko | zad. 6 | zad. 8 | 
| -------------- | ---    | ---    |
|  ...           |        |        |
|                |        |        |



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



## Zadanie 1
:::success
Autor: Rafał Spyra	
:::
![](https://i.imgur.com/gIqt722.png)
<pre>
Start:
A=1001
B=0011
P=0000

1.
i       ii
A=1001	A=1100
P=0011	P=0001

2.
i	ii
A=1100	A=1110
P=0001	P=0000

3.
i	ii
A=1110	A=0111
P=0000	P=0000

4.
i	ii
A=0111	A=1011
P=0011	P=0001

0001 1011 = 16 + 8 + 2 + 1 = 27 = 9 * 3 = 1001 * 0011
</pre>


## Zadanie 2
:::success
Autor: Aleksandra Nicpoń
:::
![](https://i.imgur.com/lDTKidB.png)
![](https://i.imgur.com/igZEljy.png)


## Zadanie 3
:::success
Autor: Ksawery Plis	
:::

![](https://i.imgur.com/SOG4dBz.png)

Algorytm podobny do tego w Zadaniu 1, z jedną różnicą:
jeśli najmniej znaczący bit A wynosi 0, to pomijamy dodawanie 0 do P i od razu robimy shift.

![](https://i.imgur.com/2rkNiy8.png)


A = 9 = 1001
B = 3 = 0011
P = 0000

1. 0000 1001 - start
2. 0011 1001 - +B
3. 0001 1100 - shift
4. 0000 1110 - shift
5. 0000 0111 - shift
6. 0011 0111 - +B
7. 0001 1011 - shift

Wynik: 0001 1011 = 1+2+8+16 = 27

## Zadanie 4
:::success
Autor: Mateusz Cerulewicz	
:::
![](https://i.imgur.com/kYTFVLD.png)

## Zadanie 5
:::success
Autor: Natalia Zychowicz	
:::
Wykorzystujemy tutaj algotytm Booth'a, czyli te zasady:
![](https://i.imgur.com/zyEUbry.png)
Struktura podobna jest do struktury z zadania 4.
![](https://i.imgur.com/F531j0G.png)

## Zadanie 6
:::danger
Autor: 
:::

## Zadanie 7
:::success
Autor: Dominik Szczepaniak	
:::

![](https://i.imgur.com/CCfPZ1F.jpg)


## Zadanie 8
:::success
Autor: Wojciech Bogucki	
:::

![](https://i.imgur.com/tX6xAPL.png)

Dla $n$-bitowych liczb wykonujemy $n$ kroków:
```c=
//0
if(P<0)
{
    //1a
    P<<1;
    P[0] = A[n-1];
    A<<1;
    //2a
    P = P + B;
}
else
{
    //1b
    P<<1;
    P[0] = A[n-1];
    A<<1;
    //2b
    P = P - B;
}
//3
if(P < 0)
    A[0] = 0;
else
    A[0] = 1;
```

| Rejestr | P(0) | A(11) | B(3) |
|-|-|-|-|
| Wartość | 00000 | 01011 | 0011 |

| Krok | P | A | Instrukcja |
| - | - | - | - |
||||
| I| **0**0000 | 01011 |$if(P<0)$| 
|  | 00000 | 1011_ |$(P,A)<<1$|
|  | 11101 | 1011_ |$P=P-B$|
|  | **1**1101 | 1011_ |$if(P<0)$|
|  | 11101 | 10110 |$A[0]=0$|
||||
|II| **1**1101 | 10110 |$if(P<0)$|
|  | 11011 | 0110_ |$(P,A)<<1$|
|  | 11110 | 0110_ |$P=P+B$|
|  | **1**1110 | 0110_ |$if(P<0)$|
|  | 11110 | 01100 |$A[0]=0$|
||||
|III| **1**1110 | 01100 |$if(P<0)$|
|   | 11100 | 1100_ |$(P,A)<<1$|
|   | 11111 | 1100_ |$P=P+B$|
|   | **1**1111 | 1100_ |$if(P<0)$|
|   | 11111 | 11000 |$A[0]=0$|
||||
|IV| **1**1111 | 11000 |$if(P<0)$|
|  | 11111 | 1000_ |$(P,A)<<1$|
|  | 00010 | 1000_ |$P=P+B$|
|  | **0**0010 | 1000_ |$if(P<0)$|
|  | 00010 | 10001 |$A[0]=1$|
||||
| V| **0**0010 | 10001 |$if(P<0)$|
|  | 00101 | 0001_ |$(P,A)<<1$|
|  | 00010 | 0001_ |$P=P-B$|
|  | **0**0010 | 0001_ |$if(P<0)$|
|  | 00010 | 00011 |$A[0]=1$|
||||

| Rejestr | P | A | B |
|-|-|-|-|
| Wartość | 00010 | 00011 | 0011 |

Niech $r_{k}$ będzie zawartością pary rejestrów (P, A) w kroku $k$, ignorując $k$ mniej znaczących bitów. W algorytmie przywracającym najpierw obliczamy $2r_k$(przesunięcie bitowe w lewo), a następnie $2r_k -2^nb$(odejmujemy B od rejestru P).
Jeśli $2r_k - 2^nb = 0$, oba algorytmy kończą krok z identycznymi wartościami w (P, A).
Jeśli $2r_k - 2^nb < 0$, wtedy algorytm przywracający przywraca to do $2r_k$, więc następny krok to $r_{res} = 2 (2r_k) - 2^nb$.
W algorytmie nieprzywracającym $2r_k - 2^nb$ jest przechowywane jako liczba ujemna, a w następnym kroku $r_{nonres} = 2(2r_k - 2^nb) + 2^nb = 4r_k - 2^nb = r_{res}$.
W ten sposób (P, A) ma te same bity w obu algorytmach.

## Zadanie 9
:::danger
Autor: 
:::
