###### 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:
### 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$ |
:::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);
}
```
Sign in with Wallet
Connect another wallet