---
# System prepended metadata

title: 'Lista 3 (18 marca 2021), grupa KBa'
tags: [kba, ask21, ćwiczenia]

---

# Lista 3 (18 marca 2021), grupa KBa

###### tags: `ask21` `ćwiczenia` `kba`

## 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     |
| --------------------:| ----- | --- | ----- | --- | ----- | --- | --- | ----- |
|        Andriy Bernad | X     | X   | X     | X   |       |     | X   |       | 5
|     Wojciech	Bogucki|       | X   |       |     |       |     | X   | X     | 3
|         Michał Doros | X     | X   | X     | X   | X     | X   |     | ==X== | 7
|        Marko Golovko |       | X   |       |     |       |     |     |       | 1
|    Magdalena Jarecka | X     | X   | X     | X   |       | X   |     |       | 5
|        Szymon Jędras |       | X   | X     |     |   X   | X   | X   | X     | 6
|     Heorhii Karpenko | ==X== | X   | X     | X   |       |     |     |       | 4
|    Szymon Kosakowski |   X   | X   |   X   |     |   X   |     |     |       | 4
|      Izabella Kozioł |       |     |       |     |       |     |     |       | 0
|   Franciszek Malinka | X     | X   | ==X== | X   | X     | X   | X   | X     | 8
|         Filip Pazera |       | X   |   X   |     |       |     | X   | X     | 4
|    Franciszek Pindel |       | X   | ==X== | X   | X     | X   | X   |       | 6
|     Kacper Puchalski | X     | X   | X     |     | X     |     |     |       | 4
|       Kacper Solecki | X     | X   | X     | X   | X     |==X==|     | X     | 7
|      Andrzej Tkaczyk |       | X   |       |     |       |     |     |       | 1
|    Łukasz Wasilewski | x     | x   | ~~x~~ |     |       |     |     |       | 2 !!
| Vladyslav Yablonskyi | X     | X   |    X  |  X  |       |     |     |       | 4
|           Adam Zyzik |       |     |       |     |       |     |     |       | 0
:::

## Zadanie 1

:::danger
Autor: Grzegorz Karpenko
:::

### Twierdzenie 1,2:
![](https://i.imgur.com/UqbT3lo.png)
### Twierdzenie 3:
![](https://i.imgur.com/ZJ76EnH.png)

**Dla dodatnich**:
$\lfloor \frac{2^{32}+2}{3}\cdot\frac{n}{2^{32}} \rfloor = \lfloor \frac{n}{3} + \frac{2n}{3\cdot2^{32}} \rfloor = \lfloor \frac{n}{3} \rfloor$


Z Twierdzenia 3:
Dla $0 \leq n < 2^{31}$ zachodzi:
$0 < 2n < 2^{32}$
$0 < \frac{2n}{3\cdot2^{32}} < \frac{1}{3}$.

**Dla ujemnych**:
$\lfloor \frac{2^{32}+2}{3}\cdot\frac{n}{2^{32}} \rfloor + 1 = \lfloor \frac{2^{32}+2}{3} \cdot \frac{n}{2^{32}} + 1 \rfloor = \lfloor \frac{2^{32}n+2n+3\cdot2^{32}}{3\cdot2^{32}}\rfloor = (Twierdzenie 1) = \lceil \frac{2^{32}n+2n+1}{3\cdot2^{32}} \rceil = \lceil \frac{n}{3} + \frac{2n+1}{3\cdot2^{32}} \rceil = \lceil \frac{n}{3} \rceil$

Z Twierdzenia 3:
Dla $-2^{31} \leq n \leq -1$ zachodzi:
$-\frac{1}{3} < \frac{2n+1}{3\cdot2^{32}} < 0$.

```c=
int32_t przez3(int32_t n){
    const int64_t M = ((1ll << 32) + 2) / 3;
    return (n * M >> 32) + (n < 0);
}

// Zamiast operatora porówniania możemy wykorzystać zgodnie z zadaniem 6 z listy 2 taki oto wzór dla prównania x<y: 
bool lessThanWithSign(int32_t x, int32 y)
{
    return (x >> 1) - (y >> 1) >> 31 & 1 | (~x & y & 1) & (x >> 1) - ((y >> 1)+1) >> 31 & 1;
}
```
> [name=Franciszek Malinka] mam bez tego porównania
> :::spoiler
> ```c
> int32_t div3(int32_t x) {
>   const int64_t M = 0X55555556;  // (2**32 + 2) / 3
>   int32_t q = (M * (int64_t)x) >> 32;
>   return q + ((q >> 31) & 1);
> }
> ```
> :::

## Zadanie 2

:::info
Autor: Marko Golovko
:::
Standard IEEE 754 określa, że binary16 ma następujący format:
* Bit znaku: 1 bit
* Szerokość wykładnika: 5 bitów
* Mantysa: 11 bitów (10 jawnie zapisanych)
* Bias: 15

1.5625*10^(−1) = 1.25 * 2^(-3)

(-1)^s * 2^(eeeee-15) * 1.mmmmmmmmmm

s = 0
e = 01100
m = 0100000000

16 . Minimalna dodatnia (subnormalna) wartość wynosi 2 ^ −24 ≈ 5,96 × 10 ^ −8. Minimalna dodatnia wartość normalna to 2 ^ −14 ≈ 6,10 × 10 ^ −5. Maksymalna reprezentowalna wartość to (2−2 ^ −10) × 215 = 65504.

32 . Minimalna dodatnia wartość normalna wynosi 2^(-126) ≈ 1.18 * 10^(-38) a minimalna dodatnia (subnormalna) wartość to 2^(-149) ≈ 1.4*10^(-45)

## Zadanie 3

:::info
~~Autor: Łukasz Wasilewski~~
:::

$
3.984375 * 10^(-1) +3.4375 * 10^(-1)+ 1.771 * 10^3

3.984375 * 10^(-1) = 0.3984375 = 51/128 = 2^(-2) * 1.10011
3.4375*10^(-1) = 0.34375 = 11/32 = 2^ (-2) *44/32=2^(-2) *(1+11/32)=2^(-2)*(1.01011)
1.771 * 10^3 = 1771 = 1024+747=2^10*(1.1011101011)

16- bitowy
2^(-2) *1.10011+2^(-2) *(1.01011)+2^10*(1.1011101011) = 2^(-2) * (1.10011+1.01011)+2^10 * (1.1011101011) =
= 2^(-2) * 10.1111000000 + 2^ 10 * 1.1011101011 = 2^(-1) * 1.01111 + 2^10 * 1.1011101011 = 2^10 *(1.0111100000 * 2^(-11)+1.1011101011)=
=2^10*(round(0.0000000000101111) + 1.1011101011) = (0.0000000001+1.1011101011)*2^10 = 1.1011101011 * 2^10 = 11011101011(binarnie, czyli dziesiętnie 1771)

po zmianie kolejności dodawań wynik się nie zmieni ponieważ jeżeli 1.771*10^3 zdominował sumę pozostałych składników to tym bardziej zdominuje
je dodawane osobno

32- bitowy
2^(-2) * 1.10011+2 ^ (-2) * (1.01011)+2^10*(1.1011101011) = 2^(-2) * (1.10011+1.01011)+2^10 * (1.1011101011) =
= 2^(-2) * 10.1111 + 2^10 * 1.1011101011 = 2^(-3)*1.01111 + 2^10 * 1.1011101011 = 2^10* (1.01111*2^(-13)+1.1011101011)=
=2^10 * (0.000000000000101111 + 1.1011101011) = 1.101110101100101111 * 2^10 =11011101011.00101111  (binarnie, czyli dziesiętnie 1771.18359375)

2^10 * (1.1011101011)+2 ^ (-2) * 1.10011+2^(-2)*(1.01011) = 2^10 * (1.1011101011 + 0.00000000000110011) + 2^(-2)*(1.01011) =
=2^10 * (1.10111010110110011 + 0.00000000000101011) = 1.10111010111011110*2^10=11011101011.00101111 (binarnie, czyli dziesiętnie 1771.18359375)

$
Jeżeli zaokrąglamy x do n bitów po przecinku to Guard Bit jest n-tym bitem po przecinku w x, Round Bit jest n+1 bitem po przecinku w x,
zaś sticky bit to wartość logiczna zdania "w x istnieją zapalone bity na pozycjach dalszych niż n+1 po przecinku".

> [name=Franciszek Malinka] mój rozw
:::spoiler
```
f1 = 0.3984375;  // 0 01101 1001100000
f2 = 0.34375;    // 0 01101 0110000000
f3 = 1771;       // 0 11001 1011101011  
```

$f_1 = 2^{-2}\cdot 1.10011_{(2)}$
$f_2 = 2^{-2}\cdot 1.011_{(2)}$
$f_3 = 2^{10}\cdot 1.1011101011_{(2)}$

\begin{align}
f_1 + f_2 = 2^{-2}\cdot 1.10011_{(2)}+2^{-2}\cdot 1.011_{(2)} = 2^{-2}(1.10011_{(2)} + 1.011_{(2)}) \\= 2^{-2}\cdot 10.11111_{(2)}=2^{-1}\cdot 1.011111_{(2)}
\end{align}
Nic sie nie psuje, to się mieści w połowie precyzji.

Kolorem $\color{blue}{niebieskim}$ oznaczamy **guard**, kolorem $\color{red}{czerwonym}$ oznaczamy **round**, kolorem $\color{green}{zielonym}$ oznaczamy **sticky**.
\begin{align}
(f_1+f_2)+f_3 &= 2^{-1}\cdot 1.011111_{(2)} + 2^{10}\cdot 1.1011101011_{(2)} \\&= 2^{10}(0.\underbrace{0000000000}_{\text{10 zer}}1011111_{(2)} + 1.1011101011_{(2)})\\&=2^{10}\cdot 1.101110101\color{blue}{1}\color{red}{1}\color{green}{011111}_{(2)}
\end{align}

Wg zasady zaokrąglania do parzystych, dostajemy ostateczny wynik 
\begin{align}(f_1 + f_2) + f_3 = 2^{10}\cdot 1.10111011_{(2)} = 1772
\end{align}

Teraz zmieniając kolejność dodawania:
\begin{align}
f_2 + f_3 &= 2^{-2}\cdot 1.011_{(2)} + 2^{10}\cdot 1.1011101011_{(2)}\\&=2^{10}(0.\underbrace{0000000000}_{\text{10 zer}}01011_{(2)} + 1.1011101011_{(2)}) \\&= 2^{10}\cdot 1.101110101\color{blue}1\color{red}0\color{green}{1011}_{(2)}
\end{align}

Guard i sticky są równe 1, ale round jest równy 0, więc zaokrąglamy w dół, zatem
\begin{align}
f_2 + f_3 = 2^{10}\cdot 1.1011101011_{(2)} = f_3
\end{align}
Teraz analogicznie dojdziemy do wniosku, że 
\begin{align}
f_1 + (f_2 + f_3) = f_1 + f_3 = f_3 = 1771.
\end{align}

**Definicja:** 
- Bit nazywamy **round** jeśli jest pierszym bitem wychodzącym poza precyzję liczby (czyli, który na rozwinięciu dwójkowym liczby jest (dł. mantysy + 1)-wszy).
- Bit **guard** to pierszy bit na lewo od **round**,
- **sticky** to bitowy $\texttt{OR}$ pozostałych, mniej znaczących bitów od **rounda**. 

:::

## Zadanie 4

:::danger
Autor: Magdalena Jarecka
:::

>Mamy zmienne «x», «y» i «z» typu «int32_t» ustawione na wybrane przez nas wartości.
>Konwertujemy je do liczb typu «double» zapisanych w zmiennych «dx», «dy» i «dz». Rozważmy poniższe wyrażenia z języka C. Wskaż, które z nich mogą obliczyć się do fałszu. Podaj kontrprzykład – konkretne wartości naszych zmiennych całkowitoliczbowych.
>
>1. (float)x == (float)dx
>2. dx - dy == (double)(x - y)
>3. (dx + dy) + dz == dx + (dy + dz) 
>4. (dx * dy) * dz == dx * (dy * dz)
>5. dx / dx == dz / dz

1. int float jest praktycznie tym samym co int na double na float
2. x = -2
   y = INT32_MAX = 2147483647
   dla x - y występuje negatywny nadmiar co w wynniku daje liczbę dodatnią, a (double)INT32_MAX dają poprawną liczbę (bez nadmiaru, dx - dy = -2147483649)
3. Skoro dx, dy i dz konwertowane wartości z int32_t to wyrażenie zawsze oblicza się do $true$.
    :::spoiler Jeśli dx, dy i dz dowolne liczby z zakresu double to dla 
    dx = 2.501
    dy = INT32_MAX
    dz = INT32_MAX
    (dx + dy) + dz = 4294967296.500999
    dx + (dy + dz) = 4294967296.501000
    > [name=Franciszek Malinka] no ale przecież te `dx, dy, dz` są konwertowane z intów, nie może być `dx = 2.501`
    >  > [name=Magdalena Jarecka] dopis poglądowy nie mający wpływu na zadanie
    :::
    Bo konwersja int -> double jest bezstratna
4. analogicznie do powyżej
6. ok, jeśli wartości są różne od 0, bo będzie jakaś liczba specjalna

> [name=Franciszek Malinka] w 4 nie zawsze jest prawda. Iloczyn intów nie musi sie już mieścić w zakresie `double`, co może generować kłopoty. Kontrprzykład:
> :::spoiler
> `x = MAX_INT, y = 0x40000006, z = MIN_INT + 110`
> -4951759928863062087929167872.000000
> -4951759928863061538173353984.000000
> :::

## Zadanie 5

:::success
Autor: Kacper Puchalski
:::

1. x ^ 0x80000000   XORujemy pierwszy bit znaku
2. ((x & 0x7f800000) >> 23) - 127    obliczamy wartość $exp-bias$
3. (x == y) | ((x | y) == 0x80000000)    x==y lub -0=+0
4. ((x >> 1) - (y >> 1) - (~x & y & 1)) >> 31  sprawdzamy znak $x/2 - y/2$ pomniejszone o 1 kiedy x jest parzyste i $y=x+1$

> [name=Franciszek Malinka] w 4. nie wystarczy sprawdzić czy `x < y`. Jeśli `f < 0` oraz `g > 0`, to nie zachodzi `x < y`.
> 4. Porównać $f$ oraz $g$: przypadki: 
> - f nieujemne, wtedy wystarczy porównać (ale na intach) czy `x < y` LUB f ujemne, wtedy wystarczy porównać (ale na uintach) czy `x > y` (jeśli `y >= 0`, to faktycznie `f < g`, bo `g > 0` oraz mamy `x > y`; jeśli `y < 0`, to `x > y` "nie patrzy" w zasadzie na bit znaków, a reszta działa tak jak normalnie).
> - obie są zerami, ale z przeciwnymi znakami. Wtedy to samo co w przykładzie 3.
> ```c
> int32_t a = x, b = y;
> f < g <=> ((a >= 0 & a < b) | (a < 0 & x > y)) & ((x|y) != 1<<31)
> ```


> [name=Kacper Solecki] 
>```c=
> uint32_t less(uint32_t x, uint32_t y){
>    reuturn ((x >> 1) - (y >> 1) - (~x & y & 1)) >> >31;
>}
>
>
>uint32_t zeros =  (x & 0x7FFFFFFF)  == 0 & (y & >0x7FFFFFFF) == 0 ^ 1; \\ przynajmniej jedno nie jest >zerem \\ x = y = 0
>x ^= 1 << 31;
>y ^= 1 << 31;
>uint32_t esx = x & 0xFF800000; // cecha i znak x>
>uint32_t esy = y & 0xFF800000; // cecha i znak y>
>uint32_t mx = x & 0x007FFFFF; // mantysa x>
>uint32_t my = y & 0x007FFFFF; // mantysa y
>
>uint32_t result = zeros & (less(esx, esy) | (less(esx, esy) ^ 1) & less(mx, my); \\ x < y)
>```

> [name=Krystian Bacławski]
> Idea jak porównać liczby o takich samych znakach?
> ```c
>   ( x &  y & (y - x))   |    (~x & ~y & (x - y))
> (x < 0 & y < 0 & x > y) | (x >= 0 & y >= 0 & x < y)  
> ```

## Zadanie 6

:::success
Autor: Kacper Solecki
:::

```c=
int32_t ex(uint32_t x){ //cecha
    return ((x & 0x7F800000) >> 23) - 127;
}

uint32_t mant(uint32_t x){ // mantysa
    return x & 0x007FFFFF; 
}

uint32_t setEx(uint32_t x, int32_t e){ //ustaw cechę
    e += 127;
    return x & 0x807FFFFF | e << 23;
}

uint32_t setMant(uint32_t x, uint32_t m){ //ustaw mantysę
    return x & 0xFF800000 | m;
}

uint32_t fshift(uint32_t x, int32_t i){
    int32_t e = ex(x); // cecha x
    e += i;
    if(i>=0){
        if(e > 127)  // cecha jest większa niz maksymalna
            return setEx(setMant(x, 0), 128); // inf (znaku x)
        return setEx(x, e); // znormalizowana
    }
    
    // i < 0:
    if(e < -126){
        uint32_t subnormShift = -e - 126;
        if(subnormShift > 23)
            return setEx(setMant(x, 0), -127);
            // 0 (znaku x), gdy przesuwamy o długość mantysy
        // 1 << 23 to jedynka, która jest "przed kropką"
        uint32_t subnormMant = (mant(x) | 1 << 23) >> subnormShift;
        return setEx(setMant(x, subnormMant), -127); // subnormalna
    }
    return setEx(x, e); // znormalizowana
}
```

## Zadanie 7

:::info
Autor: Wojciech Bogucki
:::
Najpierw ustalamy znak(jeśli wyjdzie -1, to ustawiamy na 1 i bierzemy liczbę przeciwną, bo szukamy najbardziej wiodącą jedynkę).
Funckja \_\_builtin_clz($i$) zwraca liczbę zer wiodących $i$, więc odejmujemy ją, a potem dodajemy bias.
Potem usuwamy wiodącą jedynkę odpowiednią maską.
Potem wyznaczamy wartości bitów guard, round, sticky(sticky to **OR** bitów, więc wystarczy sprawdzić czy jest większa od zera).
Na końcu obliczamy mantysę, odpowiednio przesuwając liczbę i dodająć zaokrąglenie.
Potem składamy liczbę.
```c=
int32_t int2float(int32_t i) {
    // obliczanie znaku
    int32_t s = i >> 31;
    //ustawienie znaku i poprawienie liczby
    if (s == -1) {
        i = -i;
        s = 1;
    }
    //znajdowanie jedynki wiodącej
    int32_t p = 32 - __builtin_clz(i);
    int32_t e = p - 1 + 127;   
    //usuwanie jedynki wiodącej
    i &= (1<<(p-1))-1; 

    int32_t 
        guard  = 0,
        round  = 0,
        sticky = 0; 
    //obliczanie bitów guard,round,sticky
    if (p > 24) {
        guard  = ( i >> (p - 23 - 1) ) & 1;
        round  = ( i >> (p - 23 - 2) ) & 1;
        sticky = ( i & ( ( 1 << (p - 23 - 2) ) - 1 ) ) > 0; 
    }
    //obliczanie mantysy
    int32_t mantysa = 
        ( p < 24 ? (i << (24 - p)) : (i >> (p - 24)) ) + 
        ((guard & round) | (round & sticky)) ;

    return (s << 31) + (e << 23) + mantysa ;
}
```

## Zadanie 8

:::success
Autor: Michał Doros
:::

```c=
int32_t float2int(int32_t f)
{
  int32_t s = f >> 31;               /* -1 jeśli znak był ujemny */
  int32_t e = (f >> 23 & 255) - 127; /* wykładnik po odjęciu bias */
  uint32_t m = f << 8 | INT_MIN;  /* mantysa 1.xxx... dosunięta do lewej */
  if (e <= 30 && e >= 0) //jeśli w tym zakresie to liczba mieści się w incie
  {
    m >>= (31 - e); //przesunięcie mantysy na odpowiednie miejsce
    return (int32_t)m * (1 | s); //ustawienie znaku
  }
  return INT_MIN ^ ((1u << 31) & e); //MININT jeśli e >= 30, 0 jeśli e ujemne
}
```
jeśli e ujemne to ((1u << 31) & e) = 1 << 31  więc xor z INT_MIN (1<<31) daje 0
jeśli e >= 30 to ((1u << 31) & e) = 0 więc xor z INT_MIN daje INT_MIN
