---
# System prepended metadata

title: Lista 3
tags: [ASK]

---

###### tags: `ASK`

# Lista 3


## Zadanie 1

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

<br/>

Dla liczb całkowitych $n$ i $d$ oraz liczby rzeczywistej $x$ spełnione są zależności:


$$
0 \leq x < \left|\frac{1}{d}\right| \ \ \Rightarrow \ \ \left\lfloor \frac{n}{d} + x\right\rfloor = \left\lfloor\frac{n}{d}\right\rfloor
$$

$$
-\left|\frac{1}{d}\right| < x \leq 0 \ \ \Rightarrow \ \ \left\lceil \frac{n}{d} + x\right\rceil = \left\lceil\frac{n}{d}\right\rceil
$$

$$
d > 0 \ \ \Rightarrow \ \ \left\lfloor\frac{n}{d}\right\rfloor =
\left\lceil\frac{n - d + 1}{d}\right\rceil
$$

<br/>
<br/>

Obliczamy $n \cdot M$ i bierzemy bardziej znaczące 32 bity wyniku, czyli otrzymujemy
$$
q = \left\lfloor\frac{n\cdot M}{2^{32}}\right\rfloor 
  = \left\lfloor\frac{n}{2^{32}}\frac{2^{32} + 2}{3}\right\rfloor
  = \left\lfloor\frac{n}{3} + \frac{2n}{3\cdot2^{32}}\right\rfloor
$$



Ponieważ $n < 2^{31}$, to dla $n \geq 0$ zachodzi
$$
0 \leq \frac{2n}{3\cdot2^{32}} < \frac{1}{3},
$$

więc 

$$
q = \left\lfloor \frac{n}{3}\right\rfloor
$$

<br/>

Załóżmy, że $n < 0$. Wtedy do $q$ dodajemy jeszcze $1$ i otrzymujemy
$$
q' = \left\lfloor\frac{n}{2^{32}}\frac{2^{32} + 2}{3}\right\rfloor + 1
   = \left\lfloor\frac{2^{32}n+2n+3\cdot2^{32}}{3\cdot2^{32}}\right  \rfloor
   = \left\lceil\frac{2^{32}n + 2n + 1}{3 \cdot 2^{32}}\right\rceil
   = \left\lceil\frac{n}{3} + \frac{2n+1}{3\cdot2^{32}}\right\rceil
$$

Ponieważ $-2^{32} \leq n \leq -1$, prawdziwa jest nierówność
$$
-\frac{1}{3} + \frac{1}{3\cdot2^{32}} \leq \frac{2n+1}{3\cdot2^{32}} \leq -\frac{1}{3\cdot 2^{32}}.
$$

W takim razie 
$$
q' = \left\lceil\frac{n}{3}\right\rceil
$$


## Zadanie 2

W standardzie *IEEE 754-2008* liczby 16-bitowe typu `float` (`half-precision`) są definiowane:

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



### Chcemy zapisać w `half-precision` liczbę $0.15625_{(10)}$

1. Konwersja na postać binarną:

    $0.15625 \cdot 2 = 0.3125 \space | \space 0$
    $0.3125  \cdot 2 = 0.625 \space | \space 0$
    $0.625 \cdot 2 = 1.25 \space | \space 1$
    $0.25 \cdot 2 = 0.5 \space | \space 0$
    $0.5 \cdot 2 = 1 \space | \space 1$

    $1.5625 \cdot 10^{-1} = 0.15625_{(10)} = 0.00101_{(2)} = 1.01 \cdot 2^{-3}$
2. Wartości sign, exponent i fraction:
    - $s = 0$
    - $exp = 01100_{(2)}$
        - $E = -3$
        - $bias = 2^{k-1}-1$, gdzie $k$ to liczba bitów na jakich zapisany jest $exp$
        $\to bias = 2^4-1 = 15$
        - $exp = E + bias$  
        $\to exp = -3 + 15 = 12 = 01100_{(2)}$
    - $frac = 0100000000_{(2)}$

więc otrzymamy: $0|01100|0100000000$


**Porównanie zakresu liczbowego i dokładności w stosunku do $32$-bitowego `float`:**

`half-precision`:
*    maksymalna wartość: 
$0|11110|1111111111 = 6.55 \cdot 10^4$
*    minimalna wartość: 
$1|11110|1111111111 = 6.10 \cdot 10^{-5}$
*    maksymalna zdenormalizowana: 
$0|00000|1111111111 = 2^{-14} \cdot \frac{1023}{1024} = 6.09 \cdot 10^{-6}$
*    minimalna zdenormalizowana:
$0|00000|0000000001 = 2^{-14} \cdot \frac{1}{1024} = 5.96 \cdot 10^{-8}$

`single-precision`:
*    maksymalna wartość: 
$0|11111110|11...11 = 2^{254-127} \cdot (2 - \frac{1}{2^{23}}) = 3.4 \cdot 10^{38}$
*    minimalna wartość: 
$0|00000001|00...00 = 2^{-126} = 1.1754943 \cdot 10^{-38}$
*    maksymalna zdenormalizowana: 
$0|00000000|11...11 = 2^{-126} \cdot \frac{2^{23}-1}{2^{23}} = 1.1754942 \cdot 10^{-38}$
*    minimalna zdenormalizowana:
$0|00000000|00...01 = 2^{-126} \cdot \frac{1}{2^{23}}= 1.4012 \cdot 10^{-45}$

## Zadanie 3

Standard IEEE 754-2008 z poprzedniego zadania
|   Name   |  Common name   | Significand bits | Exponent bits |  Exponent bias   |
|:--------:|:--------------:|:----------------:|:-------------:|:----------------:|
| binary16 | Half precision |        10        |       5       | $2^{5-1}−1 = 15$ |

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

:::info
Do obliczenia: $0.3984375 + 0.34375 + 1771$
:::
1. Zamiana liczb
    $0.3984375 = 0.0110011 = 2^{-2} \cdot 1.10011 \implies 0\ 01101\ 1001100000$
    $0.34375 = 0.01011 = 2^{-2} \cdot 1.011 \implies 0\ 01101\ 0110000000$ 
    $1771 = 11011101011.0 = 2^{10} \cdot 1.1011101011 \implies 0\ 11001\ 1011101011$
    ```
    Przykład zamiany liczby 0.34375
    0.34375 * 2 = 0.6875 | 0
    0.6875 * 2  = 1.375  | 1
    0.375 * 2   = 0.75   | 0
    0.75 * 2    = 1.5    | 1
    0.5 * 2     = 1      | 1

    0.01011 = 2^(-2) * 1.011
    ```
2. Sumowanie
    $(0.3984375 + 0.34375) + 1771 =\\
    2^{-2} \cdot (1.10011 + 1.011) + 2^{10} \cdot 1.1011101011 =\\
    2^{-2} \cdot 10.11111 + 2^{10} \cdot 1.1011101011 =\\
    0.1011111 + 2^{10} \cdot 1.1011101011 =\\
    2^{10} \cdot (0.00000000001011111 + 1.1011101011) =\\
    2^{10} \cdot 1.1011101011|1011111$
    
3. Zaokrąglanie
    ```
               G|RSSSSSS     
    1.1011101011|1011111
    
    G = 1
    R = 1
    S = 1
    
    Wynik:
    1.1011101100
    ```
    $2^{10} \cdot 1.1011101011|1011111 \approx 2^{10} \cdot 1.1011101100 =\\
    1772 \implies 0\ 11001\ 1011101100$

3. Sumowanie na odwrót
    $0.3984375 + (0.34375 + 1771) =\\
    2^{-2} \cdot 1.10011 + (2^{-2} \cdot 1.011 + 2^{10} \cdot 1.1011101011) =\\
    2^{-2} \cdot 1.10011 + (0.01011 + 2^{10} \cdot 1.1011101011)=\\
    2^{-2} \cdot 1.10011 + 2^{10} \cdot (0.000000000001011 + 1.1011101011)=\\
    2^{-2} \cdot 1.10011 + 2^{10} \cdot 1.1011101011|01011 \approx\\
    0.0110011 + 2^{10} \cdot 1.1011101011 =\\
    2^{10} \cdot (0.00000000000110011 + 1.1011101011) =\\
    2^{10} \cdot 1.1011101011|0110011$
        
4. Zaokrąglanie
    ```
               G|RSSSSSS
    1.1011101011|0110011

    G = 1
    R = 0
    S = 1
    ```
    $2^{10} \cdot 1.1011101011|0110011 \approx 2^{10} \cdot 1.1011101011 =\\
    1771 \implies 0\ 11001\ 1011101011$
    

## Zadanie 4

1. `(float) x == (float) dx`
   `prawda`
2. `dx - dy == (double) (x - y)`
   `x = INT_MIN, y = INT_MAX`
3. `(dx + dy) + dz == dx + (dy + dz)`
   `prawda`
4. `(dx * dy) * dz == dx * (dy * dz)`
   `x = 0xEEC46EA8, y = 0xA2CC1D15, z = 0xE881D838`
5. `dx / dx == dz / dz`
   `x = 0, y = 1`

## Zadanie 5

#### 1
```c= 
x ^ ( 1 << 31 )
```
Znak znajduje się na bicie najbardziej po lewej, XORujemy go z 1 ( 0 ^ 1 = 1, 1 ^ 1 = 0 )

#### 2
```c=
( x & 0x7f800000 ) >> 23 - 127
```
$7f800000_{16} = 01111111100000000000000000000000_{2}$
Zerujemy bity odpowiadające za mantysę i znak -> z tego wyciągamy exponent, i odejmujemy bias (żeby dostać się do rzeczywistej potęgi która stoi przy liczbie).

#### 3
```c=
(x == y) | ( ( x | y ) == ( 1 << 31 ) )
```
Wykonujemy zwykłe porównanie, ale trzeba też uwzględnić sytuację kiedy x i y są zerami (z minusem lub bez). Kiedy obie liczby = 0, to x | y da nam liczbę z zapalonym bitem najbardziej po lewej i samymi zerami. Jeśli liczba nie była zerem, to gdzieś na pozostałych bitach będą znajdować się jedynki więc porównanie po lewej zwróci fałsz.

#### 4
```c=
int32_t lessthan(uint32_t x, uint32_t y) {
    int32_t is_x_negative = (x >> 31) ^ 1;
    int32_t is_y_positive = (y >> 31) & 1;
    int32_t are_both_negative = !is_y_positive & is_x_negative;
    int32_t are_both_positive = is_y_positive & !is_x_negative;

    return ((is_x_negative & is_y_positive) |
            (are_both_positive & ((x - y) >> 31) & 1) |
            (are_both_negative & ((y - x) >> 31) & 1)) 
            & (((x | y) & 0x7FFFFFFF) != 0);
}
```
Najpierw sprawdzamy znak x i y.
Jeśli x jest ujemne a y nieujemne, to wiadomo że x < y, czyli powinniśmy zwrócić prawdę.
Jeśli obie liczby są dodatnie, to sprawdzamy znak wyrażenia x - y ( kiedy x < y, to x - y będzie ujemne (jeśli znakiem odejmowania będzie 1, to zwrócimy prawdę) ).

Jeśli obie liczby są ujemne, to sprawdzamy znak wyrażenia y - x ( przy x < y powinien być ujemny ).

$01111111111111111111111111111111_{2}=0x7FFFFFFF_{16}$

Jeśli którykolwiek ze składników alternatywy był prawdziwy, to znaczy że x < y. Trzeba jeszcze przeanalizować sytuację w której x = y.
Wtedy (x | y) zandowane z 0x7FFFFFFF będzie zerem jeśli x i y to zero albo -zero, czymś różnym od zera wpp (bo utrzymane zostaną te bity, które różnią x | y od zera). 
W końcu pozostaje sprawdzić, czy otrzymana liczba jest zerem.

Jeśli x, y = 0 lub -0 to prawy składnik tej koniunkcji będzie fałszywy (ale wtedy tak naprawdę nie musimy sprawdzać całej lewej strony bo i tak x !< y). Jeśli któraś z liczb jest różna od zera, to nie rozwali nam to całego wyrażenia, bo będziemy ANDować całą alternatywę w linijkach 7,8,9 z 1ką -> wynik | się nie zmieni.

## Zadanie 6

```c= 
uint32_t funkcja(uint32_t x, int32_t i)
{
    int32_t exp = ((x & 0x7F800000) >> 23);
    exp += i;
    if (i >= 0) 
        if (exp >= 255)
            return 0x7F800000 | (x&(1<<31));
    else
        if(exp < 0)
            return x & (1<<31)
    return (x & 0x807FFFFF) + (exp << 23);
}
```


## Zadanie 7

```c=
int32_t int2float(int32_t i) {
    if(i == INT_MIN) return 0xcf000000; // if na wykladnik rowny 2 ^ 31 // maska 158
    if(i == 0) return 0;

    int znak = (i & ((uint32_t)(1)) << 31);
    if(i < 0) i *= -1;
    uint32_t val = i;
    int leading_zeros = __builtin_clz(val);
    uint32_t wykladnik = (127 + 31 - leading_zeros);
    uint32_t mantisa_ext = (val << (leading_zeros + 1));
    uint32_t mantisa = (mantisa_ext >> 9);
    uint32_t round_bit = (mantisa_ext & (1 << 8)) > 0;
    uint32_t guard_bit = (mantisa_ext & (1 << 9)) > 0;
    uint32_t sticky_bit = (mantisa_ext & ((1<<8) - 1)) > 0;


    if(round_bit == 1){
        if(sticky_bit) mantisa++;
        else{
            if(guard_bit == 1) mantisa++;
        }
    }

    if(mantisa == (1 << 23)){
        mantisa = 0; wykladnik++;
    }

    return (znak | (wykladnik << 23) | mantisa);
}
```



## Zadanie 8

```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 | 0x80000000; /* mantysa 1.xxx... dosunięta do lewej */

    if(e<0)
        return 0;
    if(e>30)
        return 0x80000000;
    m >>= (31 - e);
    return (int32_t)m * (1 | s);
}
```

