# Lista 0 (25 lutego 2021), grupa pwit

###### tags: `ask21` `ć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!**

Tabelka zawiera tylko osoby zapisane do grupy. Osoby oczekujące proszone są o wpisanie się do osobnej tabelki poniżej.

:::warning
Z tej listy pojedyńczy student może otrzymać maks 2. punkty (bonusowe). Tabelka służy do poinformowania, kogo można tymi bonusami obdarzyć.
:::

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
|Wojciech Adamiec | X | X | X | | X | | X | X |
|Kacper Bajkiewicz | | | | | | | | |
|Bartłomiej Hildebrandt| | | | | | | | |
|Dominik Komła | | | | | | | | |
|Aleksandra Kosińska | X | X | X | | X | X | X | |
|Oleś Kulcewicz | | | | | | | | |
|Damian Lukas | | | | | | | | |
|Michał Mikołajczyk | X | X | X | | X | | | |
|Mateusz Opala | | X | X | X | X | | | |
|Łukasz Orawiec | | | | | | | | |
|Szymon Pielat | X | X | X | | X | | | |
|Łukasz Pluta | X | X | X | X |==X==| | X | |
|Kamil Puchacz | X | X | X | x | X | | | |
|Magdalena Rzepka | X | X | X | | X | ==X==| | |
|Cezary Stajszczyk | X | X | X | X | X | X | X | |
|Jakub Szajner | | | | | | | | |
|Bartosz Troszka | | | | | | | | |
|Miłosz Urbanik | X | X | X | X | X | X | | |

Tabelka dla osób oczekujących na zapis.

| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|
| | | | | | | | | |

:::

## Zadanie 1

:::info
Autor: Michał Mikołajczyk
:::
>Przekształć każdą z podanych liczb z systemu ósemkowego na system binarny, szesnastkowy i dziesiętny:

- $42_8 = 100\space010_2 = 0010\space0010_2 = 22_{16} = 34_{10}$
- $255_8 = 010\space101\space101_2 = 1010\space1101_2 = AD_{16} = 173_{10}$
- $3047_8 = 011\space000\space100\space111_2= 0110\space0010\space0111_2 = 627_{16} = 1575_{10}$
- $140336_8= 001\space100\space000\space011\space011\space110_2 = 1100\space0000\space1101\space1110_2 = C0DE_{16} = 49374_{10}$

## Zadanie 2

:::info
Autor: Mateusz Opala
:::
1.2A
2.9F
3.7F+7F=FE
4.166
:O

## Zadanie 3

:::info
Autor: Aleksandra Kosińska
:::

Wyzeruj $k$-ty bit zmiennej $x$:

x &= ~(1<<k);

Ustaw $k$-ty bit zmiennej $x$:

x |= 1<<k;

Zaneguj $k$-ty bit zmiennej $x$:

x ^= 1<<k;

## Zadanie 4

:::info
Autor: Kamil Puchacz
:::

uint32_t A(uint_32t x, uint32_t y){
    return x << y;
}

uint32_t B(uint_32t x, uint32_t y){
    return x >> y;
}

uint32_t C(uint_32t x, uint32_t y){
    return x  & ((1 << y) - 1)
}

uint32_t D(uint_32t x, uint32_t y){
    return (x >> y) + ((X << (32 - y)) > 0)
}

Hipoteza:
wynik = ((x+(1<<(y-1)))>>y)
bierzemy liczbę dodajemy do niej połowę naszego modulo i przesuwamy bitowo o y.

Uwaga: problem dla "dużych" x i y

Przykład 1:
x = 26
x = 0b(11010), y = 2

sufit(x/4) = 7
wynik =

Przykład 2:
x = 0b(11001), y = 2
problem: wynik poprawny to 7, algorytm daje odpowiedź 6

Poprawka:
wynik=((x+(1<<y)-1)>>y)
komentarz:
x=a*(1<<y)+b
dla b=0, wynik=a, dla b>0:
wynik=(a*(1<<y)+b+(1<<y)-1)>>y,
gdzie b+(1<<y)-1>=(1<<y),więc wynik=a+1

**Pytanie**: czy umiemy rozwiązać to zadanie dla x typu int32_t (a nie uint32_t).

Czy poniższy kod działa?

uint32_t A(int_32t x, uint32_t y){
    return x << y;
}

Zakłady, że x*2^y mieści się w typie int32_t.

Łatwiejsze pytanie. Załóżmy, że x < 0 oraz liczby x i 2*x mieszczą się w typie int32_t.
Pokażemy, że 2*x jest równe x << 1.

x = 0b(1a_30...a_0)

x = -2^31 + a_30*2^30 + ... + a_0 * 2^0

"x << 1" = -2^31*a_30 + 2^30*a_29 + ... + 2*a_1

Gdyby a_30 było == 0 to by oznaczało, że 2x nie mieści się w int32_t.

Pomysł:
(x jest typu int32_t)

$\lceil x/2^y \rceil=\lfloor\frac{x+(2^y - 1)}{2^y}\rfloor$

Gdy x < 0 to poniższe wyrażenie "działa":

a =`(x + (1 << y) - 1) >> y`
Gdy x >= 0 to trzeba je poprawić, bo "nie działa" dla "dużych" x. Poprawka
b = `(x + ((1 << y) - 1U) >> y`

i trzeba umieć zakodować warunek:

x < 0 ? a : b

|

## Zadanie 5

:::info
Autor: Łukasz Pluta
:::

return ((x == 0) || (x & (x - 1)));
LUB
((x-1) & (1 << 31)) | (x & (x - 1))

## Zadanie 6

:::info
Autor: Magdalena Rzepka
:::

**Big endian** - to forma zapisu danych, w której najbardziej znaczący bajt umieszcza się jako pierwszy.

**Little endian** - to forma zapisu danych, w której najmniej znaczący bajt umieszcza się jako pierwszy.


8 bitów = 1 bajt
32 / 8 = 4

uint32_t x;
uint32_t first, second, third, fourth;

first =  (x & 0x000000ff) << 24;
second = (x & 0x0000ff00) << 8;
third =  (x & 0x00ff0000) >> 8;
fourth = (x & 0xff000000) >> 24;

uint32_t answer = first | second | third | fourth;

0bmaska_bitowa

## Zadanie 7

:::info
Autor: Cezary Stajszczyk
:::

**ASCII** - siedmio bitowy system kodowania znaków; każdej liczbie przyporządkowany jest znak.

**Kody sterujące** - pierwsze 32 kody, nie odpowiadają żadnemu drukowalnemy znakowi, tylko służą do sterowania urządzeniem.

Kody sterujące ASCII:
- 0 - NULL
- 4 - EOT (end of transmission)
- 7 - sygnał dźwiękowy
- 10 - przesunięcie o jeden wiersz
- 12 - przesunięcie o jedną stronę

## Zadanie 8

:::info
Autor: Wojciech Adamiec
:::

**UTF-8** (8-bit Unicode Transformation Format) – system kodowania, wykorzystujący od 1 do 4 bajtów do zakodowania pojedynczego znaku, w pełni kompatybilny z ASCII. Jest najczęściej wykorzystywany do przechowywania napisów w plikach i komunikacji sieciowej.

Tablica ASCII ma tylko 128 znaków - do wielu celów to jest zdecydowanie za mało, UTF-8 rozwiązuje ten problem.

Kodowanie zależy od tego o jakim znaku mówimy. Dla odpowiednich przedziałów kodów korzystamy z tabeli:


Tekst do zakodowania: *Proszę zapłacić 5€!*

50 72 6f 73 7a c4 99 20 7a 61 70 c5 82 61 63 69 c4 87 20 35 e2 82 ac 21

Dla przykładu popatrzmy na €:

1. Kod dla € to U+20AC.
2. Jest to przedział między U+0800 a U+FFFF, więc potrzebujemy 3 bajtów.
3. $20AC_{16} = 0010 \space 0000 10\space10 1100_2$.
4. Korzystamy z tabeli w taki sposób, że w miejsce każdego $x$ wstawiamy kolejne bity.
5. Dostajemy na koniec takie kodowanie: $1110 \space 0010 \space 1000 \space 0010 \space 1010 \space 1100$
6. Co konwertujemy do systemu szesnastkowego: $1110 \space 0010 \space 1000 \space 0010 \space 1010 \space 1100 = E2 \space 82 \space AC$