path: root / src / teaching / upp-2025 / week14 / bitwise-and-binary-representation.du

'def title Побитови операции и представяне на числени данни - УПП, Седмица 14, 15.01.2026
'def  desc Презентация върху размери на типове данни, 1s complement, 2s complement и IEEE754

# {title}

{pagenav 4 min;13 January 2026;14 January 2026}

{presentation-controller}

:title_slide

# Побитови операции и представяне на числени данни


:slide35

## Какво е бит?

{br4}

:unordered

- всичко в компютъра се представя в двоична бройна система

- {i бит} е най-малката единица памет

- {i байт} (byte) е най-малката {b адресируема} единица памет

- {i дума} (word) е най-голямата {b обработваема} единица памет




Размерите на тези стойности (и някои други ефекти) се определят от архитектурата на процесора:

:slide35

{br3}

:unordered

- На {b модерни} процесори:
  {` x86-64} (Intel/AMD), {` ARM} (Apple M series/Snapdragon/Exynos/Cortex)\n
  байт е 8 бита, дума е 64 бита

- процесора извършва повечето инструкции върху {i думи}

- в повечето архитектури, размера на един адрес ({b указател}) е една {i дума}

- {` bool} заема един {i байт}, въпреки че стойността му може да се побере в един {i бит}



Общо взето, за модерен процесор/ОС/... може да използвате размерите в долната таблица.

.warn
{b Обаче}, стандарта на C++ определя единствено {i минимален} размер за типовете.
Долните стойности не са закон!

:slide35

{br2}

:table
:2

|= Тип
|= Размер

|: {` bool}, {` char}
|: "1" бит (1 байт)

|: {` short}
|: 16 бита (2 байта)

|: {` int}, {` float}
|: 32 бита (4 байта)

|: {` long}
|: 32 бита {url Windows;https://learn.microsoft.com/en-us/windows/win32/winprog/windows-data-types#LONG}, 64 бита MacOS/Linux

|: {` long long}, {` double}
|: 64 бита (8 байта)




:slide35

## Побитови оператори

{br4}

.p
Аритметичните оператори извършват аритметика върху целите стойности на числата

.p
Побитовите оператори извършват {i логически} операции върху всеки два {i съответни} бита



:slide35

### Побитово "И" {` &}, "ИЛИ" {` |}, "НЕ" {` ~}

.p
Работят като логическите {` &&}, {` ||}, {` !} но върху битовете.
Разглеждайки две еднобайтови числа:

```
10010011 & 10011100 = 10010000
10010011 | 10011100 = 10011111
         ~ 10010011 = 01101100

### Побитово "изключващо или" {` ^}

.p
Истина, когато двата бита са различни и лъжа, когато са еднакви

```
10010011 ^ 10011100 = 00001111


:middle_slide35

### Отместване наляво {` <<}

.p
Отместваме битовете с {` n} на брой позиции на ляво

```
10010011 << 1 = 00100110
10010011 << 2 = 01001100
10010011 << 3 = 10011000


:middle_slide35

### Отместване надясно {` >>}

.p
Отместваме битовете с {` n} на брой позиции на дясно.\n
Ако типа е {` unsigned}:

```
10010011 >> 1 = 01001001
10010011 >> 2 = 00100100

.p
Иначе повтаряме водещия бит:

```
01010011 >> 1 = 00101001
10010011 >> 1 = 11001001
10010011 >> 2 = 11100100


:slide35

## Представяне на цели числа

{br4}

:unordered

- "unsigned" цели числа са ясни (стандартното преобразуване между двоична и десетична бройна система)

- всеки бит репрезентира степен на 2

- как обаче да представим отрицателни числа?



:middle_slide35

.p
Идея: {b старшия бит} (най-левия) да определя дали е положително или отрицателно

```
000  0
001  1
010  2
011  3
100 -0
101 -1
110 -2
111 -3


:middle_slide35

.p
Проблем: нормалното събиране {b не} работи

```
 1 +  1 = 001 + 001 =  010 =  2
 1 + -1 = 001 + 101 =  110 = -2
-1 + -1 = 101 + 101 = 1010 =  2 (отрязваме)

.p
Не би ли било готино да представим числата, така че събиране/изваждане да работи по {i същия} начин?


:slide

### 1s complement

{br1}

.p
Отрицателното число е като положителното, но с {b обратните} битове

```
000  0
001  1
010  2
011  3
100 -3
101 -2
110 -1
111 -0

.p
Нарича се така, защото {` x & -x} винаги е равно на {` 111...111}


:middle_slide35

```
 1 +  1 = 001 + 001 =  010 =  2
 1 + -1 = 001 + 110 =  111 = -0
-1 + -1 = 110 + 110 = 1100 = -3 (отрязваме)

.p
Последната сума ни е грешна, защото се нуждаем от "end-around carry".
Бита който "прелива" трябва да се събере обратно в числото.

```
-1 + -1 = 110 + 110 = 1100 = 1 + 100 = 101 = -2

.p
{b Плюсове:} водещия бит е единица при отрицателни.\n
{b Минуси:} има +0 и -0, нуждаем се от "end-arround carry".


:slide

### 2s complement

{br1}

.p
Като 1s complement, но при отрицателните числа изваждаме единица.

```
000  0
001  1
010  2
011  3
100 -4
101 -3
110 -2
111 -1

.p
Нарича се така, защото {` x + -x} е равно на 2 на степен броя битове


:middle_slide35

```
 1 +  1 = 001 + 001 =  010 =  2
 1 + -1 = 001 + 111 = 1000 =  0 (отрязваме)
-1 + -1 = 111 + 111 = 1110 = -2 (отрязваме)

.p
Събиране/изваждане работят по същия начин, винаги водещия бит е единица при отрицателни, няма -0.


:slide35

## Представяне на числа с плаваща запетая

{br1}

.p
Идея: цяло число, в което закодираме позиция на точката.

.p
Например, в 16-битово число, левите 4 бита закодират позицията на точката сред битовете, останалото е числото.

```
0000 001001010110 -> 001001010110. = 598.0
0010 001001010110 -> 0010010101.10 = 149.2
1010 001001010110 -> 00.1001010110 = 0.598


:slide35

{br3}

:unordered

- Много малък обхват от числа: най-голямо е 4095.0, най-малкото е 0.0, най-прецизното е 0.0001

- Ако използваме 2s complement за отрицателни числа, обхвата става от -2048.0 до 2047.0

- Имаме много нули

- 4те бита за позиция са wasted, защото най-лявата позиция е 12, {` 1100}



:slide35

### IEEE754

{br1}

.unordered
- Формат, публикуван през {url 1985;https://en.wikipedia.org/wiki/IEEE_754-1985} година
- За 16 бита, обхвата му е от -65504 до 65504, най-прецизното възможно число е 0.000000059604645
- Поддържа "числата" безкрайност и "not a number"
- Представя числата като дроби (научна нотация)
- {b Не всички числа в обхвата могат да бъдат представени}
- Числата около нулата могат да имат много цифри след запетаята, тези по-далеч могат по-малко


:middle_slide35

.p
Сложен е, любознателните могат да го разучат:

.unordered
- {url https://mathcenter.oxford.emory.edu/site/cs170/ieee754/}
- {url https://www.h-schmidt.net/FloatConverter/IEEE754.html}
- {url https://en.wikipedia.org/wiki/Half-precision_floating-point_format#Half_precision_examples}
- {url https://codingnest.com/the-little-things-comparing-floating-point-numbers/}