Преговор - УПП, Седмица 4, 27.10.2023



Функции и алгоритмични задачи

От сега нататък ще направим няколко промени

Нещата за 2s compliment се намират и в преговора на миналата седмица, ама го написах след като свърши часа, затова го копирам и тук.

2s compliment

Интуитивно обяснение на 2s compliment. Да приемем, че работим с тип данни, при който имаме само 3 бита.

Как бихме ги използвали, за да представим отрицателните числа? Най-лесния начин е да погледнем най-левия (старшия) бит, ако е 0 значи е положително, ако е 1 значи е отрицателно, тоест 010 е 2, докато 110 е -2. Ако разпишем всичките ни числа:

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

Това работи, обаче имаме един гигантски проблем: събирането не работи! От математика знаем, че “2 - 1 = 2 + (-1)”, тоест би трябвало да можем да съберем побитово 2 и -1 и да получим 1. Ама,

2 + -1 = 010 + 101 = 111 = -3

Също, знаем, че “(-1) + (-1) = -2”, обаче

-1 + -1 = 101 + 101 = 1010 имаме overflow, това се съкращава на 010 = 2

Излиза, че с тази схема не можем да събираме отрицателни числа както събираме положителни (или както събираме побитово).

Да не говорим, че ние имаме -0, което не ни трябва много.

Нека да помислим пак, да вземем само положителните:

011 3
010 2
001 1

Сега, искаме -1 да бъде такова число, различно от досега дефинираните (тоест което има единица в старшия си бит) така че “1 + -1 = 0”. Лесно се досещаме, че ако добавим към “001” числото “111”, тогава тяхната сума ще предизвика overflow и резултата ще бъде 0:

001 + 111 = 1000 overflow, става 000

Нека тогава “-1 = 111”.

Правейки същото за “2 + -2”, намираме че

010 + 110 = 1000 overflow, става 000

Нека тогава “-2 = 110”. За “3 + -3” се досещаме, че “-3 = 101”. За сега имаме:

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

100 не сме го използвали, обаче намерихме отрицателното число за всяко положително. Да видим как работим с него, побитово “100 + 001 = 101”, тоест “x + 1 = -3”, следователно x ще бъде -4.

Това е идеята на “complements”, дефинираме отрицателни числа, така че да използваме едно и също събиране между положителни и отрицателни.

Още от много старите “калкулатори” (сумиращи машини), изваждането се е свеждало до събиране на положително и отрицателно число.

И това е причината защо ~ 2 връща -3:

~ 00000000000000000000000000000010
──────────────────────────────────
  11111111111111111111111111111101

И затова при >> със знаков тип имаме аритметическо отместване:

11111111111111111111111111111101 >> 1
─────────────────────────────────────
11111111111111111111111111111110

Функции

Позволяват ни да групираме редове код. Синтаксисът е следния:

<ВЪРНАТ ТИП> име(<АРГУМЕНТИ>) {
    тяло
}

Като <АРГУМЕНТИ> са двойки от типа ТИП ИМЕ, разделени със запетаи. Един вид, аргументите са променливи към тяло, които задаваме извън функцията.

Извикваме функция чрез име(<СТОЙНОСТИ>), като <СТОЙНОСТИ> са разделени със запетая и всяка съответства на поредния тип в аргументите на функцията. Там, където пишем име(<СТОЙНОСТИ>) се “замества” с върнатата стойност от функцията.

Връщаме стойност като напишем във функцията return СТОЙНОСТ;.

Една функция трябва да бъде декларирана преди да бъде използвана, тоест кода

#include <iostream>

int main() {
    std::cout << doSomething();
}

int doSomething() {
    ...
}

Няма да се компилира. Можем само да декларираме функция, без да я дефинираме (тоест без да и дадем тяло) чрез синтаксиса:

<ВЪРНАТ ТИП> име(<АРГУМЕНТИ>);

Тоест горния пример ще работи ако имаме:

#include <iostream>

int doSomething();

int main() {
    std::cout << doSomething();
}

int doSomething() {
    ...
}
︽