diff options
1 files changed, 132 insertions, 3 deletions
| -rw-r--r-- | src/teaching/upp-2023/week3/revision.md | 135 |
diff --git a/src/teaching/upp-2023/week3/revision.md b/src/teaching/upp-2023/week3/revision.md index 0ef3687..cb0ac61 100644 --- a/src/teaching/upp-2023/week3/revision.md +++ b/src/teaching/upp-2023/week3/revision.md @@ -2,11 +2,11 @@ &&presentation -&&clide &¢ered +&&clide &&font35 &¢ered # Цикли, assert -&&/centered &&/clide +&&/centered &&/font &&/clide @@ -89,6 +89,135 @@ &&slide +## 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 +``` + +&&/slide + + + +&&clide + +Това работи, обаче имаме един гигантски проблем: събирането не работи! +От математика знаем, че "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, което не ни трябва много. + +&&/clide + + + +&&clide + +Нека да помислим пак, да вземем само положителните: + +``` +011 3 +010 2 +001 1 +``` + +Сега, искаме -1 да бъде такова число, различно от досега дефинираните (тоест което има единица в старшия си бит) така че "1 + -1 = 0". +Лесно се досещаме, че ако добавим към "001" числото "111", тогава тяхната сума ще предизвика overflow и резултата ще бъде 0: + +``` +001 + 111 = 1000 overflow, става 000 +``` + +Нека тогава "-1 = 111". + +&&/clide + + + +&&slide + +Правейки същото за "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. + +&&/slide + + + +&&clide + +Това е идеята на "complements", дефинираме отрицателни числа, така че да използваме едно и също събиране между положителни и отрицателни. + +Още от много старите "калкулатори" ([сумиращи машини](https://en.wikipedia.org/wiki/Adding_machine)), изваждането се е свеждало до събиране на положително и отрицателно число. + +И това е причината защо `~ 2` връща `-3`: + +``` +~ 00000000000000000000000000000010 +────────────────────────────────── + 11111111111111111111111111111101 +``` + +И затова при `>>` със знаков тип имаме аритметическо отместване: + +``` +11111111111111111111111111111101 >> 1 +───────────────────────────────────── +11111111111111111111111111111110 +``` + +&&/clide + + + +&&slide + ## Цикли &&lineb4 @@ -239,7 +368,7 @@ &&lineb2 -- `continue`: продължи след края на сегашната итерация; тоест изпълнението на тяло се прекратява и заповаме нова итерация +- `continue`: продължи след края на сегашната итерация; тоест изпълнението на тяло се прекратява и започваме нова итерация При `for` цикли директно отива на инкрементация |