---
# System prepended metadata

title: 'Lista 2 (11 03 2021), grupa pwit'
tags: [pwit, ask21, ćwiczenia]

---

# 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
![](https://i.imgur.com/C7Giqff.png)
:::

```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;
```


