###### tags: `ASK`

# Lista 2

## Zadanie 1

(x > 0) || (x - 1 < 0)

wyrażenie zwróci *fałsz*

dla x = $INT32\_MIN$ (wartość możemy sprawdzić po dołączeniu biblioteki `stdint.h`), które jest równe $100...00_{(2)} = -2147483648$
$x > 0 \to false$
$x - 1 = 100...00_{(2)} - 1 = 011...11_{(2)} = 2147483647 = INT32\_MAX$
występuje *overflow*, więc $x - 1 < 0 \to false$

(x & 7) != 7 || (x << 29 < 0)

wyrażenie zawsze zwróci *prawdę*

$(x \& 7) \ != 7 \to$ będzie fałszem, gdy wszystkie trzy skrajnie prawe bity $x$ będą równe $1$
weźmy $x =\ ...111{(2)}$
wtedy po przesunięciu $x << 29$ otrzymamy $111....00_{(2)}$
widzimy, że jest to liczba ujemna, czyli $(x << 29 < 0) \to true$

(x * x) >= 0

wyrażenie zwróci *fałsz*

gdy w wyniku $x^2$ na 31 pozycji w reprezentacji binarnej będzie zapalony bit, znaleźć taką liczbę możemy w następujący sposób (uwzględniając dziedziny):
\begin{cases}
x^2 = (2^t + 2^r)^2 = 2^{2t} + 2^{t+r + 1} + 2^{2r}\\
t + r + 1 = 31
\end{cases}
weźmy np. $x = 2^{10} + 2^{20} = 1049600 = 00000000000100000000010000000000_{(2)}$
$x^2 = (2^{10} + 2^{20})^2 = 2^{20} + 2^{31} + 2^{40}$
po utracie bitów wyniku zapalone będą bity $31$ i $20 \to$ liczba ujemna

x < 0 || -x <= 0

wyrażenie zawsze zwróci *prawdę*

ponieważ liczb ujemnych jest o jeden więcej

x > 0 || -x >= 0

wyrażenie zwróci *fałsz*

dla $x = INT32\_MIN$

`-x = ~x + 1`
$-x = -INT32\_MIN = -(-2147483648) = 2147483648 =\\
= INT32\_MAX + 1 = 011...111 + 1 = 10...000 = INT32\_MIN$

(x | -x) >> 31 == -1

wyrażenie zwróci *fałsz*

dla $x = 0$
$(x \ | -x)$ zwróci $0$, a $(0 >> 31)$ to też $0$

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

wyrażenie zawsze zwróci *prawdę*

ponieważ `unsigned` jest zarażający to nastąpi niejawne rzutowanie, czyli tak naprawdę nasze wyrażenie będzie wyglądać tak:
`(uint32_t)(x + y) == (uint32_t)y + (uint32_t)x`

x * ~y + (uint32_t)y * (uint32_t)x == -x

wyrażenie zawsze zwróci *prawdę*

`(uint32_t)x * (uint32_t)(~y) + (uint32_t)y * (uint32_t)x == (uint32_t)(-x)`

Lewa strona:
`(uint32_t)x * ((uint32_t)(~y) + (uint32_t)y)`
korzystając z : `-y = ~y + 1` $\to$ `-1 = ~y + y` mamy:
`(uint32_t)x * (-1)`
`(uint32_t)x * UINT32_MAX` $\to$ zwraca `(uint32_t)(-x)`

Prawa strona:
`(uint32_t)(-x)`
`(uint32_t)(~x + 1)`

## Zadanie 2

Sposób z dodawaniem:

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

Sposób z xorem:

void swap(int *x, int *y) {
  *x ^= *y;
  *y ^= *x;
  *x ^= *y;
}

## Zadanie 3

**Nadmiar (overflow)** - przekroczenie zakresu wartości, które może przyjąć zmienna (liczba zajmuje więcej bitów pamięci, niż zostało jej przydzielone)

**Niedomiar (underflow)** - dla liczb typu *integer* oznacza, że wartość wyniku jest bliższa minus nieskończoności niż minimalna wartość jaki może przyjąć dana zmienna

zakładam, że $x, y, s$ są typu `int32_t`

- jeżeli $x$ i $y$ mają rózne znaki to nie może wystąpić *overflow*
- jeżeli $x,y > 0$ to w wyniku 31 bit będzie zapalony
- jeżeli $x,y < 0$ to w wyniku 31 bit będzie zgaszony

(((s ^ y) & (s ^ x)) >> 31) & 1;

## Zadanie 4

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

$x * 3/4 = x * (1/2 + 1/4) = x * 1/2 + x * 1/4 = x / 2 + x/2^2$

int32_t threefourths(int32_t x){
    x = ((x >> 1) + (x >> 2)) + (1 & x & (x >> 1));
}

druga część sumy sprawdza czy dwa bity po prawej są oba zapalone $\to$ utrata bitu wyniku i trzeba dodać 1

## Zadanie 6

((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

`-x = ~x + 1`

int abs(int x) {
  int64_t mask = x >> N - 1;
  return mask & ~x+1 + ~mask & x;
}

## Zadanie 8

`-x = ~x + 1`

int sign(int x){
  return (x >> N-1) | (~x+1 >> N-1 & 1);
}

## Zadanie 9

z xor'em:

int32_t odd_ones(uint32_t x) {
    x ^= x >> 1;
    x ^= x >> 2;
    x ^= x >> 4;
    x ^= x >> 8;
    x ^= x >> 16;
    return x & 1;
}

wykorzystując zadanie z poprzedniej listy zliczające liczbę zapalonych bitów:

int32_t odd_ones(uint32_t x) {
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555); // 01010101010101010101010101010101
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // 00110011001100110011001100110011
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); // 00001111000011110000111100001111
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); // 00000000111111110000000011111111
  x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF); // 00000000000000001111111111111111

  return x & 1;
}