---
# System prepended metadata

title: 'Ćwiczenia 3, grupa śr. 17-19, 8 marca 2023'
tags: [pwit, ćwiczenia, ASK23]

---

# Ćwiczenia 3, grupa śr. 17-19, 8 marca 2023

###### tags: `ASK23` `ć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!**


:::danger
|                        | 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   |
| ----------------------:| --- | --- | --- | --- | --- | --- | --- | --- | --- | 
| Mikołaj Balwicki       |     |     |     |     |     |     |     |     |     |
| Kamila Goszcz          |  X  |  X  |  X  |     |     |     |  X  |  X  |  X  |
| Mateusz Materek        |  X  |  X  |     |     |  X  |  X  |  X  |  X  |==X==|
| Mikołaj Łabędzki       |     |     |     |     |     |     |     |     |     |
:::

**Tutaj można dodeklarować zad. 9 i zad. 10 z listy 1:**
|Imię i Nazwisko | zad. 9 | zad. 10 |
| -------------- | ----   | ----    |
|       ...      |        |         |
|                |        |         |
 



:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::




## Zadanie 1
:::success
Autor:	Kamila Goszcz	
:::

- `(x > 0) || (x - 1 < 0)`
dla `x = INT32_MIN` mamy `(INT_MIN32 > 0) || (INT32_MAX < 0)` co obliczy się do fałszu
    
- `(x & 7) != 7 || (x << 29 < 0)`
pierwsza część jest prawdziwa gdy `x != bbbbb111` tzn. x nie kończy się trzema jedynkami, druga część jest prawdziwa, gdy `x = bbbbb1bb` oznacza to, że dla dowolnego `x` wyrażenie jest prawdziwe

- `(x * x) >= 0`
może nastąpić przepełnienie, a co za tym idzie jeden z bitów liczby zamiast być zwykłym bitem stanie się bitem znaku, gdy będzie to `1` to otrzymamy liczbę ujemną np. 
`10101010101010101010101010101010 * 10101010101010101010101010101010 = 11100011100011100011100011100100`

- `x < 0 || -x <= 0`
prawda

- `x > 0 || -x >= 0`
dla `x = INT32_MIN` mamy `INT32_MIN > 0 || INT32_MIN >= 0` co wylicza się do fałszu

- `(x | -x) >> 31 == -1`
dla `x = 0` mamy `0 | 0 >> 31 == 0`

- `x + y == (uint32_t)y + (uint32_t)x`
prawda, algorytmy dodawania zmiennych typu `int32_t` oraz `uint32_t` są identyczne, jedyna różnica jaka występuje to interpretacja wyniku

- `x * ~y + (uint32_t)y * (uint32_t)x == -x`
Równoważnie możemy zapisać: `x * (~y + (uint32_t)y) == -x` 
oraz `x * (uint_32)(-1) == -x` 
oraz `x * 11111... == -x`
a to dla dowolnego `x` jest prawdziwe

## Zadanie 2
:::success
Autor:	Mateusz Materek	
:::
![](https://i.imgur.com/vQzfhwF.png)

```c=
    x = x ^ y;
    y = y ^ x;
    x = x ^ y;
```

Rozwiązanie z użyciem sumy:
```c=
x = x + y;
y = x - y;
x = x - y;
```

1. Najpierw wpisujemy do zmiennej `x` sumę zmiennych `x` i `y`. 
2. Następnie do zmiennej `y` zapisujemy wartość `x - y = x' + y' - y' = x'`, zatem zmienna `y` trzyma już poprawną wartość. 
3. Teraz do zmiennej `x` zapisujemy wartość `x - y = x' + y' - x' = y'`. Zatem zmienna `x` również trzyma poprawną wartość.

## Zadanie 3
:::success
Autor:	Kamila Goszcz	
:::

:::info 
Nadmiar i niedomiar występują gdy dodajemy odpowiednio zbyt duże lub zbyt małe liczby aby wynik zmieścił się w zmiennej tego samego typu. Aby wykryć takie zachowanie muszą zajść poniższe warunki:
- liczby muszą być tego samego znaku
- wynik musi być innego znaku
:::

porównanie znaku liczb: 
`(~(x ^ y) >> 31) & 1`

porównanie znaku x i sumy: 
`(((x + y) ^ x) >> 31) & 1`

porównanie znaków liczb i sumy: 
`((~(x ^ y) & ((x + y) ^ x)) >> 31) & 1`
związzwiąz
inne rozwiązanie:
`s = x + y;
return (((s ^ x) & (s ^ y)) >> 31) & 1;`


## Zadanie 4
::danger
Autor:	
:::

|   a3|  a2 |  a1 |   a0| = x
|   b3|  b2 |  b1 |   b0| = y
|a3+b3|a2+b2|a1+b1|a0+b0|

x+y=?

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

|z3|z2|z1|z0|

najstarszy bit każdej z liczb z1 może być równy 1 -- bo to jest przeniesienie z poprzednim bitów sumy.

c   d
0 + 0 = suma 0 i przeniesienie 0
0 + 1 = suma 1 i prz. 0
1 + 0 = suma 1 i prz. 0
1 + 1 = suma 0 i prz, 1
jeśli c i d są bitami to c^d = wartośc sumy  

z = ((x ^ y) & 0x80808080) ^ z


Odejmowanie:

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


## Zadanie 5
:::success
Autor:	Mateusz Materek
:::
![](https://i.imgur.com/Y6dNQcb.png)

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

floor(3x/4) = floor(x - x/4) = x + floor(-x/4) = x - ceil(x/4)



floor(x/4) = x >> 2

floor(-1/2) = -1
floor(-1/2) = -ceil(1/2) = -1


jeśli 4 dzieli x to ceil(x/4) = floor(x/4) = x >> 2
wpp. ceil(x/4) = floor(x/4) + 1

ostatecznie
ceil(x/4) = x >> 2 + ((x & 1) | ( (x & 2) >> 1)
czyli 
x - ceil(x/4) = x - (x >> 2) - ((x & 1) | ( (x & 2) >> 1)



## Zadanie 6
:::success
Autor:	Mateusz Materek	
:::
![](https://i.imgur.com/OT1KJKE.png)

```c=
return ((x >> 1) - (y >> 1) - (~x & y & 1)) >> 31;
```

## Zadanie 7
:::success
Autor:	Kamila Goszcz	
:::

:::info
na potrzeby zadania zmienna `x` z przykładów będzie typu `int8_t`
:::

```c= 
y = x >> 31 
return y & (-x) + ~y & x 
```
```
1. dla x >= 0:
   x = 0bbbbbbb
   y = 00000000
   return 00000000 + x 
```
```
2. dla x < 0:
   x = 1bbbbbbb
   y = 11111111
   return -x + 00000000 
```

## Zadanie 8
:::success
Autor:	Kamila Goszcz	
:::

```c=
(x >> 31) | ((-x >> 31) & 1);
```
- dla `x > 0`:
```
x = 01001100
x >> 7 = 00000000
(-x >> 7) & 1 = (10110100 >> 7) & 1 = 11111111 & 1 = 00000001
(x >> 31) | ((-x >> 31) & 1) = 00000001
```

- dla `x = 0`: 
```
x >> 7 = 00000000
(-x >> 7) & 1 = (00000000 >> 7) & 1 = 00000000 & 1 = 00000000
(x >> 31) | ((-x >> 31) & 1) = 00000000
```

- dla `x < 0`: 
```
x = 11001100
x >> 7 = 11111111
(-x >> 7) & 1 = (00110100 >> 7) & 1 = 00000000 & 1 = 00000000
(x >> 31) | ((-x >> 31) & 1) = 11111111
```

## Zadanie 9
:::success
Autor: Mateusz Materek	
:::
![](https://i.imgur.com/tAr4iiz.png)

Robimy praktycznie to samo, co w zadaniu 1 z L1, tylko wynik ANDujemy z `1`:
```c=
const uint32_t m1  = 0x5555555555555555; // 0101...
const uint32_t m2  = 0x3333333333333333; // 00110011...
const uint32_t m4  = 0x0f0f0f0f0f0f0f0f; // 00001111...
const uint32_t m8  = 0x00ff00ff00ff00ff; // 8 x 0, 8 x 1...
const uint32_t m16 = 0x0000ffff0000ffff; // 16 x 0, 16 x 1.


int32_t odd_ones(uint32_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 );
    x = (x & m2 ) + ((x >>  2) & m2 );
    x = (x & m4 ) + ((x >>  4) & m4 );
    x = (x & m8 ) + ((x >>  8) & m8 );
    x = (x & m16) + ((x >> 16) & m16);
    return x&1;
}

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