# Lista 2 (11 03 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.
:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| --------------------:| --- | --- | --- | --- |:---:|:---:| --- |:---:|:---:|
|Wojciech Adamiec | X | X | X | |==X==| | X | X | X |
|Kacper Bajkiewicz | X | ==X== | X | | X | X | X | X | X |
|Bartłomiej Hildebrandt| X | X | X | | | X | X | X | |
|Dominik Komła | X | X | X | X | X | X | X | X | X |
|Aleksandra Kosińska | X | X | X | | X | | X | X | X |
|Oleś Kulczewicz | X | X | X | | X | X | X | X | X |
|Damian Lukas | X | X | X | | X | X | X | | |
|Michał Mikołajczyk | X | X | X | | X | | X | X | X |
|Mateusz Opala | X | X | X | X | X | X | X | X | X |
|Łukasz Orawiec | X | X | X | | X | X | X | X | X |
|Szymon Pielat | X | X | X | | X | |==X==| X | X |
|Łukasz Pluta | X | X | X | X | X | X | X | X | X |
|Kamil Puchacz | X | X | X | | X | X | X | X | X |
|Magdalena Rzepka | X | X | X | X | X | X | X | X | X |
|Cezary Stajszczyk | X | X | X | | X | | X |==X==| X |
|Jakub Szajner | X | X | X | | X | X | X | X | X |
|Bartosz Troszka | X | ==X== | X | | X | X | X | X | X
|Miłosz Urbanik | X | X | 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: Damian Lukas
:::
Czy wyrażenia zawsze wyliczają się do prawdy dla `x, y` będących typu `int32_t`?
* `(x > 0) || (x - 1 < 0)`
Weźmy $x = 100...00_{(2)} = -2147483648 = \text{INT_MIN}$, czyli najmniejszą możliwą wartość dla `int32_t`. Wtedy `x > 0` jest fałszem. Obliczmy drugie wyrażenie z alternatywy:
$x-1 = 100...00_{(2)}-1 = 0111...11_{(2)} = 2147483647 = \text{INT_MAX}$. Otrzymujemy również fałsz dla `x - 1 < 0`, czyli wyrażenie nie zawsze oblicza się do prawdy.
* `(x & 7) != 7 || (x << 29 < 0)`
Zwracana wartość wyrażenia `(x & 7) != 7` będzie prawdą, jeżeli chociaż jeden z trzech najmniej znaczących bitów `x` będzie zgaszony. Weźmy więc $x=b_{31}b_{30}\dots b_{3}111_{(2)}$ (dający fałsz w lewym podwyrażeniu), a następnie przesuńmy o $29$ bitów w lewo - otrzymana liczba ma wartość $11100\dots 000_{(2)}$, a więc jest ujemna, czyli wyrażenie zawsze zwróci prawdę.
* `(x * x) >= 0`
Weźmy $x=2^{16}+2^{14}$. Wtedy $x^2 = 2^{32}+2\cdot2^{30}+2^{28}=2^{32}+2^{31}+2^{28}$. Chcąc zapisać tą wartość z wykorzystaniem przesunięć bitowych, mielibyśmy `x = (1 << 32) + (1 << 31) + (1 << 28)`, co dałoby nam liczbę ujemną, jako że `(1 << 32) = 0`, `(1 << 31) = INT_MIN`, a `abs(INT_MIN) > abs(1 << 28)`. To oznacza, że wyrażenie nie zawsze obliczy się do prawdy.
* `x < 0 || -x <= 0`
To wyrażenie zawsze obliczy się do prawdy, jako że liczb ujemnych w `int32_t` jest o jedną więcej od dodatnich.
* `x > 0 || -x >= 0`
Fałsz dla $x = \text{INT_MIN}$. Lewa strona oczywista, rozpiszmy jednak prawą. Obliczmy
$$-x = -\text{INT_MIN} = -(-2147483648) = 2147483648 \\= \text{INT_MAX} + 1 = 011...111 + 1 = 10...000 = \text{INT_MIN}$$
Otrzymujemy więc w całym wyrażeniu fałsz.
* `(x | -x) >> 31 == -1`
Fałsz dla $x=0$. `(x | -x)` obliczy się do zera, przesunięcie arytmetyczne w prawo sprawi, że uzyskamy liczbę $00...000$, która nie jest równa $-1$.
* `x + y == (uint32_t)y + (uint32_t)x`
Rzutowanie zmiennych do `unsigned` jest "zaraźliwe", tzn. całe wyrażenie jest rzutowane do `unsigned`, przez co otrzymujemy `(uint32_t)(x + y) == (uint32_t)y + (uint32_t)x`. Otrzymana wartość jest zawsze prawdziwa.
* `x * ~y + (uint32_t)y * (uint32_t)x == -x`
Musimy udowodnić własność
`(uint32_t)x * (uint32_t)(~y) + (uint32_t)y * (uint32_t)x == (uint32_t)(-x)`. Wyciągnijmy więc `(uint32_t)x` przed nawias, dzięki czemu uzyskamy
`(uint32_t)(~y) + (uint32_t)y = UINT32T_MAX`, a pomnożenie `(uint32_t)x * UINT32T_MAX` zwróci nam wartość `UINT32T_MAX - (uint32_t)x`, co jest równe wartości `(uint32_t)(-x)`.
`~y = -y - 1`
## Zadanie 2
:::info
Autor: Kacper Bajkiewicz
:::
```c=
x = x ^ y;
y = x ^ y;
x = x ^ y;
```
W linijce 1 używając XORa w zmiennej x przechowujemy x ^ y.
Wtedy w 2ciej linijce mamy y = (x ^ y) ^ y i z łączności XORa wychodzi x ^ (y ^ y) = x ^ 0 = x.
W 3tej linijce za x wstawiamy (x ^ y) ^ x = (y ^ x) ^ x = y ^ (x ^ x) = y ^ 0 = y.
Czyli końcowa wartość zmiennej x to początkowy y a końcowa wartość zmiennej y to początkowy x.
Wersja z odejmowaniem/dodawaniem:
```c=
x = x + y;
y = x - y;
x = x - y;
```
## Zadanie 3
:::info
Autor: Bartłomiej Hildebrandt
:::
> Napisz wyrażenie zawierające wyłącznie zmienne «x», «y» i «s», którego wartością logiczną jest odpowiedź na pytanie czy wykonanie instrukcji «s = x + y» spowodowało nadmiar (ang. overflow) lub niedomiar (ang. underflow).
**Nadmiar** (ang. overflow) - przekroczenie zakresu wartości, które może przyjąć zmienna.
```c=
uint32_t x = 1 << 31;
x *= 2; // Overflow!
```
**Niedomiar** (ang. underflow) - wartość, na której działamy jest tak mała, że wzięta z niej wartość bezwzględna jest mniejsza niż najmniejsza liczba większa od zera możliwa do zapisania w tej zmiennej. Dla `int` nie ma możliwości wystąpenia niedomiaru.
```c=
float x = 1e-30;
x /= 1e20; // Underflow!
```
Instrukcja:
```c=
s = x + y
```
Sumowane operandy o tym samym znaku mogą zwrócić wynik przeciwny w stosunku do operandów. Zatem przy założeniu, że obydwa operandy są tego samego znaku wystarczyłby następujący kod.
```c=
((s >> 31) ^ (x >> 31) & 1)
```
W powyższej operacji porównujemy za pomocą operacji `xor` znak wyniku `s` oraz znak zmiennej `x` i jeżeli znaki są takie same to znaczy, że nie doszło do przepełnienia i zostanie zwrócone 0, wpp. 1.
Natomiast chcemy, aby algorytm działał też dla różnych znaków.
Algorytm sprawdzający czy powstał nadmiar czy niedomiar:
```c=
((s ^ x) & (s ^ y) >> 31) & 1
```
Sprawdzamy różnicę (xor) wyniku z `x` i analogicznie z `y`. Musi wystąpić różnica bitu znaku w obydwu zmiennych, więc robimy iloczyn bitowy. Następnie przesuwamy o 31 miejsc w prawo i uzyskujemy bit znaku.
- Dla x,y > 0 powyższy algorytm zwróci 1, gdy wystąpi nadmiar, bo najbardziej znaczący bit zmieni się na 1, więc otrzymamy liczbę ujemną
- Dla x,y < 0 suma s przy nadmiarze (ujemnym) będzie miała 0 na najbardziej znaczącym bicie
- Dla x < 0, y >= 0 oraz x >= 0, y < 0 sprawdzanie czy wystąpił nadmiar czy niedomiar nie ma sensu
Przykład (z przepełnieniem):
```c=
x = 0111, y = 0001
s = 1000
s ^ x = 1111, s ^ y = 1001
(s ^ x) & (s ^ y) = 1001
1001 >> 31 -> 00...1
00...1 & 1 = 1
```
## Zadanie 4
:::info
Autor: Dominik Komła
:::
```c=
uint32_t sum = (x & 0x7F7F7F7F) + (y & 0x7F7F7F7F);
sum ^= ((x ^ y) & 0x80808080);
uint32_t diff = (x | 0x80808080) - (y & 0x7F7F7F7F);
diff ^= ((0x80808080 ^ x) ^ y) & 0x80808080;
```
Przykład dodawania:
x = 1001
y = 1111
sum = (x & 0111) + (y & 0111) = 0001 + 0111 = 1000
sum ^= (x ^ y) & 1000
Przykład odejmowania:
x = 1001
y = 1111
diff = 1001 - 0111 = 0010
## Zadanie 5
:::info
Autor: Wojciech Adamiec
:::
:::info
:::
```c=
int32_t threefourths(int32_t x)
{
int32_t result = (x >> 1) + (x >> 2);
int z = (x & 2) >> 1 & (x & 1); # Jeśli 2 odcinane bity są zapalone - dodaj 1
result += z;
return result;
}
```
W naszym rozwiązaniu dodajemy $1/4 \cdot x$ do $1/2 \cdot x$ dostając $3/4 \cdot x$. Jedyny problem może się pojawić, gdy oba bity, które obcieliśmy przesunięciem bitowym były zapalone. Wówczas do wyniku musimy dodać 1.
Empiryczny dowód poprawności:
https://godbolt.org/z/Taceo4
Alternatywne rozwiązanie:
Niech x = 4i + r, i -- całkowite, r = 0, 1, 2, 3
podłoga(3x/4) = podłoga(3(4i +r)/4) = podłoga(3i + 3r/4) = 3i + podłoga(3r/4)
i = x >> 2
r = (x & 3) <- todo: czy to jest poprawne (spoiler: tak)
wynik = 3(x>>2) + ( 3(x & 3) >> 2)
Przykład obliczenia r dla liczby ujemnej
x = -5
x = 4*(-2) + 3
U2(-5) = 11011
U2(-8) = 11000 + 00011 =11011
## Zadanie 6
:::info
Autor: Łukasz Orawiec
:::
```c
((x >> 1) - (y >> 1) - (~x & y & 1) >> N - 1) & 1;
```
Sprawdzamy znak `x/2 - y/2`.
Jeśli najmniej znaczące bity `x` i `y` to odpowiednio `0` i `1`, odejmujemy jeszcze `1`.
Dla liczb bez znaku, jeśli `x < y`, to `x/2 - y/2` ma również zapalony najbardziej znaczący bit:
```
x/2 - y/2 = (2^N - 1) + 1 + x/2 - y/2 = 2^N - (y/2 - x/2) >= 2^(N-1)
```
## Zadanie 7
:::info
Autor: Szymon Pielat
:::
```c=
int32_t mask = (x >> 31);
return (mask & -x) + (~mask & x);
```
Dla x < 0: mask będzie 1111....1
Dla x => 0: mask będzie 00000...0
* W przypadku gdy x >= 0:
return 0 + (1111....1 & x)
* W przypadku gdy x < 0:
return (1111....1 & -x) + 0
-x = ~x + 1
Jakie wartości przyjmuje mask? Odp: albo 0 albo -1
~x = x ^ 1111111111111111111 (32 jedynki)
wynik = (x ^ mask) - mask
## Zadanie 8
:::info
Autor: Aleksandra Kosińska
:::
`-x = ~x + 1`
```c=
int sign(int x){
return (x >> N-1) | (~x+1 >> N-1 & 1);
}
```
## Zadanie 9
:::info
Autor: Łukasz Pluta
:::
```c=
int32_t odd_ones(uint32_t x){
// to samo co na poprzedniej liscie praktycznie
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
// x jest teraz rowne liczbie szukanych bitow
return (x & 1);
}
```
Wersja z XOR
```cpp=
x = x^x>>1;
x = x^x>>2;
x = x^x>>4;
x = x^x>>8;
x = x^x>>16;
return x&1;
```
Google Drive
Gist
Clipboard
Sign in with Wallet
