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

## Zadanie 1

:::info
Autor: Łukasz Wasilewski
:::
(x>0) || (x-1 < 0) - nie zawsze prawda. Fałsz gdy x w zapisie bitowym jest równy 100...0 bo wtedy x<0 oraz x-1 wylicza się do 011...1 co dla zmiennych typu int32_t jest większe od 0

(x&7) != 7 <=>któryś z 3 ostatnich bitów x nie jest zapalony.
x << 29 < 0 <=> 3 ostatni bit jest zapalony
więc cały warunek jest fałszywy dla cokolwiek000, cokolwiek001, cokolwiek010, cokolwiek011

(x*x)>=0 fałsz gdy (pierwszy_bit*(2^32 )-x)^2 % 2^32 >=2^(31)

x<0 || -x<=0 zawsze
x > 0 || -x >= 0 fałsz dla 10000...0_2

(x | -x)>> 31 == -1 fałsz dla 10000...0_2

x + y == (uint32_t)y + (uint32_t)x zawsze

x * ~y + (uint32_t )y * (uint32_t)x == -x zawsze bo maszynowe l. całkowite z + i * są pierścieniem, oraz ~y+(uint32_t )y=~y+y=-1.

## Zadanie 2

:::info
Autor: Wojciech Bogucki
:::

void swap(int32_t * x, int32_t * y){
    *x = *x + *y;
    *y = *x - *y;
    *x = *x - *y;
}

W lini nr. 3 efektywnie będzie y = x + y - y
=> y = x
W lini nr. 4 efektywnie będzie x = x + y - x
=> x = y
> [name=Andrzej Tkaczyk] z xorem w spoilerze

:::spoiler

x = x ^ y;
y = x ^ y;
x = x ^ y;

:::
## Zadanie 3

:::info
Autor: Magdalena Jarecka
:::

**Nadmiar** - gdy w reprezentacji liczb binarnych nie ma wystarczającej liczby bitów, aby przedstawić wynik operacji arytmetycznej.
**Niedomiar** - gdy w reprezentacji liczb binarnych ujemnych nie ma wystarczającej liczby bitów, aby przedstawić wynik operacji arytmetycznej.

s = x + y
bool is_overflow = ((s ^ y) & (s ^ x)) >> 31;

1) Jeśli x i y mają różne znaki nie może dojść do nadmiaru/niedomiaru
W tym momencie s będzie przyjmowało znak x lub y dzięki czemu (s ^ y) oraz (s ^ x) będzie różniło się najbardziej znaczącymi bitami. Czyli (s ^ y) & (s ^ x)) przy najstarszym bicie będzie miało 0.
(s ^ y) & (s ^ x)) >> 31) = 0
0 & 1 = 0
3) Jeśli mają te same znaki to może dojśc do nadmiaru/niedomiaru
Wtedy s będzie miało inny znak niż x i y.
- x, y < 0, s > 0:
Wtedy s ^ y będzie miało na początku 1 tak samo jak i s ^ x.
(s ^ y) & (s ^ x) -> również 1 na początku
Przesuwamy początkowy bit na pierwsze miejsce co sprawia że:
(s ^ y) & (s ^ x)) >> 31) = 1
1 & 1 = 1
- x, y > 0, s < 0:
Tak samo
> [name=Andrzej Tkaczyk]
> można bez & 1 na końcu

## Zadanie 4

:::info
Autor: Szymon Jędras
:::

//• ⊕ jest operacją dodawania,
z_i = (x_i ^ y_i) & 0x80 ^ ((x_i & 0x7f) + (y_i & 0x7f));


//• ⊕ jest operacją odejmowania.
z_i = ~(((x_i ^ y_i) | 0x7f) ^ ((x_i | 0x80) - (y_i & 0x7f));

Wizualizacja:
:::spoiler
$$
\begin{aligned}
&carry: &1\ 0\quad &1\ 0\quad &1\ 0\quad &1\ 0\\
&x: &1\ 1\quad &1\ 1\quad &0\ 0\quad &0\ 0\\
&y: &1\ 1\quad &0\ 0\quad &1\ 1\quad &0\ 0\\
&wynik\ pierwszy: &0\ 1\quad &0\ 1\quad &0\ 1\quad &0\ 1\\\\
&not\ x: &0\ 0\quad &0\ 0\quad &1\ 1\quad &1\ 1\\
&(not\ x)\oplus y: &1\ 1\quad &0\ 0\quad &0\ 0\quad &1\ 1\\
&koncowy\ wynik: &1\ 0\quad &0\ 1\quad &0\ 1\quad &1\ 0\\
&spodziewany\ wynik:\quad &1\ 0\quad &0\ 1\quad &0\ 1\quad &1\ 0
\end{aligned}
$$
:::
Fragment:

(x_i & 0x7f) + (y_i & 0x7f)            // (1)

maskuje najbardziej znaczący bit w każdym bajcie, uniemożliwiając overflow. Następnie pozostała część to 1-bitowa suma, najpierw znajduje te bity które się różnią pomiędzy x i y, a potem je odwraca jeżeli jakiś bit "przelał się" z mniej znaczących bitów.

Żeby wynik nie był "zły", trzeba by było przechowywać carry bit w zewnętrznej zmiennej i dodać/odjąć go w fragmencie (1).

(x_i & 0x7f) + (y_i & 0x7f) + carry;            // (1)

Carry bit można było by liczyć za pomocą takiego fragmentu kodu:

carry = (x_i & y_i ^ z_i)>>31 & 1;

:::spoiler
dodawanie:

z = (x & 0x7F7F7F7F) + (y & 0x7F7F7F7F);
z = ((x ^ y) & 0x80808080) ^ z;

odejmowanie:

z = (x | 0x80808080) - (y & 0x7F7F7F7F);
z = (((~x) ^ y) & 0x80808080) ^ z;

:::

## Zadanie 5

:::info
Autor: Andrzej Bernad
:::

$temp_{x} =\lfloor \frac{x}{2} \rfloor +\lfloor \frac{x}{4} \rfloor + \epsilon = \frac{x}{2} + \frac{x}{4}$

int32_t threefourths(int32_t x)
{
    int32_t temp_x = (x >> 1) + (x >> 2); 
    // temp_x = x / 2 + x / 4 = 3/4 * x
    
    int32_t overflow_bits = 0xC0000000 & temp_x; 
    // zapamiętujemy 2 najbardziej znaczące bity wyniku
    
    /* obliczamy wynik z możliwą utratą dwóch najbardziej 
     * znaczących bitów, natomiast z dobrym zaokrągleniem */
    int32_t temp = x;
    temp <<= 1; // x * 2
    temp +=  x; // x * 2 + x
    temp >>= 2; // (x * 2 + x) / 4 , w tym miejscu zaokrąglamy wynik
    
    // odzyskujemy dwa najbardziej znaczące bity wyniku
    temp &= 0x3FFFFFFF //0b0011..11
    temp |= overflow_bits;
    return temp;
}

// 0xC0000000 = 0b11000000000000000000000000000000

> [name=Franciszek Pindel] może tak
:::spoiler

r = (x & 0b11) + (x & 0b1) >> 2;
return (x >> 2) + (x >> 1) + r;

:::

> [name=Franciszek Malinka] mam jeszcze krócej
:::spoiler

/* Oblicz x * 3 / 4 zaokrąglając w dół */
int32_t threefourths(int32_t x) {
    return (x>>1) + (x+1 >> 2);
}

1. $x = 0 \mod 4$, wtedy $$\lfloor 3x/4\rfloor = 3x/4 = x/2 + x/4 = \lfloor x/2 \rfloor + \lfloor (x+1)/4 \rfloor$$.
2. $x = 1 \mod 4$, wtedy $$\lfloor 3x/4\rfloor = (3x - 3)/4 = 3(x-1)/4 = (x-1)/2 + (x-1)/4 = \lfloor x/2 \rfloor + \lfloor (x+1)/4 \rfloor$$.
3. $x = 2 \mod 4$, wtedy $$\lfloor 3x/4\rfloor = (3x - 2)/4 = 3x/4 - 1/2 = x/2 + x/4 - 1/2 = \lfloor x/2 \rfloor + \lfloor x/4 \rfloor \\= \lfloor x/2 \rfloor + \lfloor (x+1)/4 \rfloor$$
4. $x = 3 \mod 4$, wtedy $$\lfloor 3x/4\rfloor = (3x - 1)/4 = x/2 + x/4 - 1/4 = \lfloor x/2 \rfloor + 1/2 + \lfloor (x+1)/4 \rfloor - 1/4 -1/4 \\= \lfloor x/2 \rfloor + \lfloor (x+1)/4 \rfloor$$
:::

## Zadanie 6

:::info
Autor: Andrzej Tkaczyk
:::

$x<y\ wtw. \frac{x}{2}<\frac{y}{2}\ wtw. \frac{x}{2}-\frac{y}{2}<0$
ale psuje się jak y = x+1 i 2|x (przez zaokrąglenie), dlatego jeśli nie wychodzi porównanie $\frac{x}{2}<\frac{y}{2}$, to sprawdzamy ten przypadek y = x+1 i 2|x

uint32_t lta(uint32_t x, uint32_t y){
  return (x >> 1) - (y >> 1) >> 31 & 1 | (~x & y & 1) & (x >> 1) - ((y >> 1)+1) >> 31 & 1;
  //(x >> 1) - (y >> 1) >> 31 & 1 -> sprawdzenie czy x/2 - y/2 < 0
  //(~x & y & 1) -> sprawdzenie czy 2|x i czy y ma potencjał być x+1
  //(x >> 1) - ((y >> 1)+1) >> 31 & 1 -> sprawdzenie czy x/2 - (y+1)/2 < 0
}

int32_t ltb(int32_t x, int32_t y){
  return (x >> 1) - (y >> 1) >> 31 & 1 | (~x & y & 1) & (x >> 1) - ((y >> 1)+1) >> 31 & 1;
  //(x >> 1) - (y >> 1) >> 31 & 1 -> sprawdzenie czy x/2 - y/2 < 0
  //(~x & y & 1) -> sprawdzenie czy 2|x i czy y ma potencjał być x+1
  //(x >> 1) - ((y >> 1)+1) >> 31 & 1 -> sprawdzenie czy x/2 - (y+1)/2 < 0
}

> [name=Krystian Bacławski] Rozwiązanie do rozważenia:
:::spoiler

((x >> 1) - (y >> 1) - (~x & y & 1)) >> 31

:::

## Zadanie 7

:::info
Autor: Władysław Jabłoński
:::
* $x < 0$: `x` na najbardziej znaczącym bicie ma wartość $1$, a więc maska ma wartość równą $111...111_{(2)}$. L = -x i R = 0.
* $x \geq 0$: Wartość `mask` będzie równa 0. L = 0 i R = x

int32_t mask = x >> 31;
return (mask & -x) + (~mask & x);

> [name=Franciszek Malinka] Mam krócej
:::spoiler

int32_t y = x >> 31;
return (x ^ y) - y; 

Jeśli `x < 0`, to `y = 0xffffffff = -1`, zatem `(x^y) = ~x`, a `~x + 1 = -x`. Jeśli `x >= 0`, to `y = 0` i działania z `y` nic nie robią.

:::

## Zadanie 8

:::info
Autor: Kacper Solecki
:::

// obliczanie sgn(x)
(x >> N-1) | (-x >> N-1 & 1)

- Dla x<0 to -1 | 0. (Dla x = INT_MIN to -1 | 1)
- Dla x=0 to 0 | 0.
- Dla x>0 to 0 | 1.

## Zadanie 9

:::info
Autor: Franciszek Malinka
:::

Pomysł jest podobny do zliczania liczby zapalonych bitów. Tym razem chcemy w kubełkach trzymać liczbę parzystą, jeśli w kubełku jest parzyście wiele bitów i l. nieparzystę w p.w.

$b = x_0 \oplus x_1 \oplus x_2 ... \oplus x_{31}$

`b = x ^ (x >> 16)`

$b_i = x_i \oplus x_{i+16}$, gdzie $i = 0..15$

int32_t odd_ones(uint32_t x) {
    uint32_t y = x;
    // na co drugim bicie jest zapalona 1 iff w kubełkach dwubitowych jest nieparzyście wiele zapalonych bitów
    y = y ^ (x >> 1);        
    y = y ^ (y >> 2);
    y = y ^ (y >> 4);
    y = y ^ (y >> 8);
    y = y ^ (y >> 16);
    return y & 1;
}