C, PHP, VB, .NET

Още от училище сме научени да смятаме с десетична бройна система. В историята на човечеството е позната употребата и на други бройни системи (остатъци от които има и до днес), но десетичната е тази, която се налага практически в целия свят. Едва ли има нужда да обясняваме как се смята с нея – всеки четящ тази статия би трябвало да знае за цифрите от 0 до 9, от които се образуват числа, с които може да се събира, изважда, умножава и дели.

Двоичната бройна система се основава на същите правила. Тя съдържа само и единствено две цифри – 0 и 1. За стандартните математически операции важат следните правила:

• 0+0=0;
• 0+1=1; 1+0=1;
• 1+1=10;
• 0*0=0;
• 0*1=0; 1*0=0;
• 1*1=1.

Ако например имаме числото 10011 и трябва да го съберем с 11001, ще получим следното (на първия ред в скоби са показани пренасянията, които се получават от 1+1 = 10):

[math]\begin{matrix}
& (1)& & & (1) & (1) & \\
& & 1 & 0 & 0 & 1 & 1 \\
+ & & 1 & 1 & 0 & 0 & 1 \\
\hline
& 1 & 0 & 1 & 1 & 0 & 0 \\
\end{matrix}[/math]

Аналогично можем да умножаваме двоични числа:

[math]\begin{matrix}
& & & 1 & 0 & 0 & 1 & 1 \\
* & & &    &    & 1 & 0 & 1 \\
\hline
& & & 1 & 0 & 0 & 1 & 1 \\
+ & &0& 0 & 0 & 0 & 0 &   \\
+& 1 & 0 & 0 & 1 & 1 &&\\
\hline
&1 &0 &1 &1 &1 &1&1\\
\end{matrix}[/math]

Вече виждате много сходства между основните операции. Събирането и умножението не би трябвало да ви затруднят въобще. Колкото до изваждането – там ще се натъкнем на добре познатия проблем от ваденето на десетични числа – когато не ви достига и трябва „да вземете назаем“ единица от съседчето от ляво, т.е. да пренесете единица от ляво надясно. При двоичните числа се прави по същия начин (отбелязваме пренасянето със *)

[math]\begin{matrix}
&    &    & *  &    &   \\
& 1 & 1 & 1 & 0 & 1 \\
– & 1 & 0 & 0 & 1 & 1 \\
\hline
& 0 & 1 & 0 & 1 & 0 \\
\end{matrix}[/math]

Виждате, че във втората позиция (от дясно-наляво) цифрата на умаляемото е 0, а от нея трябва да извадим 1. Именно тук се налага пренасяне – взимаме наличната единица от трета позиция във втора. Там тя трябва да се разглежда като две единици от по-ниския ред (*), и тъй като изваждаме едната от тях, остава само една и в резултата на втора позиция пишем цифрата 1.

(*) когато правите пренасяне при изваждане на десетични числа, вие правите същото – взимайки единицата от eдна позиция в съседна, вие я разглеждате не като единица, а като десетка. При двоичната бройна система положението е същото – просто  трябва да осъзнаете, че в двоичната бройна система 10 – 1 = 1. Това е така, защото 10 в двоична бройна система всъщност е числото 2 в десетична – ще видите разяснението по-долу.

Помните ли как в десетичната бройна система всяко число можеше да се представи като сбор от степени на числото 10? Например:

[math]1923 = 1*10^3 + 9*10^2 + 2*10^1 + 3*10^0[/math]

„Числото 10“ всъщност е първото по-голямо от най-голямата цифра в десетичната бройна система – цифрата 9. По аналогия всяко двоично число може да се представи като сбор от степените на първото по-голямо число от най-голямата двоична цифра. Но кое е това число?

Знаем, че най-малкото двоично число е 0. Следващото е 1. Нямаме повече цифри, следвателно следващото число трябва да е двуцифрено. Най-малкото такова е 10. Следващото е 11. По-следващото пък трябва вече да е трицифрено – то е числото 100. Следват 101, 110 и 111. По-нататък 1000, 1001, 1010, 1011, 1100, 1101, 1111 и т.н. Нека направим една таблица, в която в първия ред ще напишем поредицата от първите 16 двоични числа и на нея съпоставим първите 16 десетични числа:

[math]\begin{matrix}
\hline
0 & 1 & 10 & 11 & 100 & 101 & 110 & 111 & 1000 & 1001 & 1010 & 1011 & 1100 & 1101 & 1110 & 1111 \\ \hline
0 & 1 & 2  & 3  & 4   & 5   & 6   & 7   & 8    & 9    & 10   & 11   & 12   & 13   & 14   & 15   \\
\hline
\end{matrix}
[/math]

Както ще видите по-долу при метода за конвертиране на десетични в двоични числа и обратно, тази таблица ще се окаже с пълно съответствие на числата. Наистина двоичното 10 е равно на десетичното 2.

От сега нататък за удобство ще слагаме долен индекс ₁₀ за десетичните числа и долен индекс ₂ за двоичните. Правете разлика между 10₂ и 10₁₀. Първото е двоичното число 10, а второто е десетичното число 10. Нека се върнем на въпроса – всяко двоично число може да се представи като сбор от степени на 10₂. Ето пример за представяне на двоично число:

[math]1101_2 = (1*10^3+1*10^2 +0*10^1+1*10^0)_2[/math]

Тук за степените използваме десетични числа (0,1,2,3) защото повдигането на степен е операция, която не зависи от бройната система. Приемете, че като пишем (10³)₂ имаме предвид (10*10*10)₂ = 1000₂. Нека опростим израза в десните скоби и да видим какво се получава:

[math](1*10^3+1*10^2+1*10^0)_2 = (1*1000 + 1*100 + 1)_2 = 1101_2[/math]

Тоест дотук (неслучайно) имаме пълна аналогия между операциите в двете бройни системи – те просто са едни и същи. Остана да покажем как можем да преобразуваме числа от десетична в двоична бройна система. Това става изключително лесно след като вече знаем горните два принципа – просто трябва да заменим 10₂ от представянето на двоичното число с числото 2₁₀! Например ако искаме да видим на колко е равно 1101, ще имаме:

[math]1101_2 = (1*10^3+1*10^2 +1*10^0)_2 = (1*2^3+1*2^2+1*2^0)_{10}=13_{10}[/math]

Аналогиите не свършват дотук. Може да проверите, че удвояването на едно двоично число (събирането му със самото себе си, което е еквивалентно на умножението му по двоичното число 10₂) е много лесно – просто добавяме една нула в края на числото. По аналогичен начин за да умножим едно десетично число по 10₁₀ просто трябва да добавим 0 в края на числото.

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

[math]1903_{10} = (1*10^3 + 9*10^2 + 3*10^0)_{10} = (1*1010^3+1001*1010^2+11)_2 = 11101101111_2[/math]

Нека проверим като го конвертираме обратно:

[math]11101101111_2 = (1*2^0 + 1*2^1+1*2^2+1*2^3+1*2^5+1*2^6+1*2^8+1*2^9+1*2^{10})_{10} = 1903_{10}[/math]

Вторият начин е може би по-лесен за употреба от страна на човек – взимаме десетичното число и започваме да го делим на 2, като помним остатъците от всяко деление (ще ги ограждаме в скоби):

1903 : 2 = 951 (1)
951 : 2 = 475 (1)
475 : 2 = 237 (1)
237 : 2 = 118 (1)
118 : 2 = 59 (0)
59 : 2 = 29 (1)
29 : 2 = 14 (1)
14 : 2 = 7 (0)
7 : 2 = 3 (1)
3 : 2 = 1 (1)
1 : 2 = 0 (1)

Сега просто взимаме остатъците отдолу нагоре това е и търсеното двоично число: 11101101111₂ = 1903₁₀.

Време е да се прехвърлим и при последната все още неразгледана операция с двоични числа – делението. Ако трябва да пресмятаме на ръка, то също е аналогично на делението при десетичните числа:

[math]\begin{matrix}
&1&0&1&0&1&0&:&1&1&1&=&1&1&0\\
-& &1&1&1& & & & & & & & & & \\
\hline
&0&0&1&1&1& & & & & & & & & \\
-& & &1&1&1& & & & & & & & & \\
\hline
& & &0&0&0& & & & & & & & & \\
-& & &0&0&0& & & & & & & & & \\
\hline
& & &0&0&0&0& & & & & & & &
\end{matrix}[/math]

Тук имахме деление без остатък. Виждате, че е напълно аналогично на делението при десетичните числа. Естествено възможно е накрая да остане остатък, т.е. число различно от 0.

Дотук обаче работихме само с цели числа. А какво се случва при реалните? Там положението не е по-различно. Например ако искаме да превърнем 57,25₁₀ в двоично, ще трябва да разделим работата на две стъпки. Първо ще превърнем 57₁₀ в двоично по познатия вече начин:

[math]57_{10} = 111001_{2}[/math]

За числото след десетичната запетая се досещаме, че:

[math]0,25_{10} = (2*10^{-1}+5*10^{-2})_{10}[/math]

Пренасяйки се върху по-удобния за нас – втори – метод за превръщане на десетични в двоични числа, можем да се досетим, че просто трябва да заменим делението с умножение (степените са станали отрицателни). Освен това, понеже се намираме след десетичната запетая, за „остатъци“ ще приемаме единиците в цялата част на числата – ще я премахваме и ще я ограждаме в скоби. Получаваме:

0,25 * 2 = 0,50 (0 – цялата част на числото е 0)
0,50 * 2 = 0,00 (1)
0,00 – спираме

Тук взимаме тези „остатъци“ в прав ред =>

[math]0,25_{10} = 0,01_{2}[/math]

От тук получаваме, че

[math]57,25_{10} = 111001,01_{2}[/math]

Когато говорим за реални числа обаче нещата не винаги са толкова прости. Нека разгледаме друг, по-сложен пример. Трябва да превърнем 12,3₁₀ в двоично число. Знаем, че 12₁₀ = 1100₂. За частта след десетичната запетая пресмятаме:

0,3 * 2 = 0,6 (0)
0,6 * 2 = 0,2 (1)
0,2 * 2 = 0,4 (0)
0,4 * 2 = 0,8 (0)
0,8 * 2 = 0,6 (1)
0,6 * 2 = 0,2 (1)
0,2 * 2 = 0,4 (0)
0,4 * 2 = 0,8 (0)
0,8 * 2 = 0,6 (1)
…

Виждаме, че буквално „не му се вижда края“ – зациклихме и никога няма да стигнем до 0,00. Е, това е добре познатия ни „период“, който познаваме при десетичните числа. Или можем спокойно да кажем, че:

[math]12,3_{10}=1100,0(1001)_2[/math]

Това са и първите малко по-неинтуитивни връзки между двете бройни системи – понякога числа с краен брой цифри трябва да се представят чрез безкрайни приближения. За математиците това е нещо напълно нормално – всеки математик знае, че при десетичните числа 0,9999(9) = 1 :)

Обратното преобразуване на реални числа – от двоична към десетична бройна система – се получава лесно по познатия вече начин. Например:

[math]101,011_{2} = (1*2^2 + 0*2^1 + 1*2^0 + 0*2^{-1} + 1*2^{-2} + 1*2^{-3})_{10}\\
= (4+1+\frac{1}{4}+\frac{1}{8})_{10}=5,375_{10}[/math]

Проверка: За цялата част:

5:2 = 2 (1)
2:2 = 1 (0)
1:2 = 0 (1)

След десетичната запетая:

0,375 * 2 = 0,750 (0)
0,750 * 2 = 0,500 (1)
0,500 * 2 = 0,000 (1)

 

За финал ще покажем един от „триковете“, които се използват при компютрите – бързо умножаване. Вече видяхме, че всяко число може да се представи като сбор от степени на двойката. Например 17₁₀ = (1+16)₁₀. Можем да го представим във вид на таблица по следния начин:

[math]\begin{matrix}17\\
=\\
1*\underline{1}+\\
0*2+\\
0*4+\\
0*8+\\
1*\underline{16}
\end{matrix}[/math]

Или за по-изчистен вид просто слагаме едно под друго степените на двойката, като в сбора ще участват само тези, които са подчертани:

[math]\begin{matrix}17\\
=\\
\underline{1}\\
2\\
4\\
8\\
\underline{16}
\end{matrix}[/math]

Нека сега да пожелаем да умножим това число по 20. В съседна колона записваме 20 и на всеки ред го удвояваме:

[math]\begin{matrix}17&&20\\
=&&\Downarrow\\
\underline{1}&&20\\
2&&40\\
4&&80\\
8&&160\\
\underline{16}&&320
\end{matrix}[/math]

Взимаме само числата от дясно, които съответстват на подчертаните вляво:

[math]\begin{matrix}17&&20\\
=&&\Downarrow\\
\underline{1}&\Rightarrow&\textbf{20}\\
2&&40\\
4&&80\\
8&&160\\
\underline{16}&\Rightarrow&\textbf{320}
\end{matrix}[/math]

Като ги съберем, получаваме отговора: 17*20 = 320+20 = 340

Така виждаме, че умножението може да бъде получено много лесно чрез операции от събиране. Първо за левите числа степените на двойката се получават много лесно – 1, 10, 100, 1000, т.н., т.е. просто се добавя нула в края на числото. Отдясно също имаме удвояване – то също е просто добавяне на нула в края на числото – 10100, 101000, 1010000, 10100000, т.н. Това определено опростява конструкцията на ALU на процесора и прави операцията умножение много по-проста.

Абсолютно по подобен начин може да се извърши бързо деление. Нека например искаме да разделим 1125 на 25. Съставяме таблица подобна на горната, но този път гледаме в обратна посока:

[math]\begin{matrix}1125&&25\\
–&&–\\
\underline{1}&\Leftarrow&\textbf{25}\\
2&&50\\
\underline{4}&\Leftarrow&\textbf{100}\\
\underline{8}&\Leftarrow&\textbf{200}\\
16&&400\\
\underline{32}&\Leftarrow&\textbf{800}
\end{matrix}[/math]

В лявата колона сме подредили степените на двойката, а в дясната сме удвоявали числото на което делим. Спрели сме до 800, защото следващото 1600 вече е по-голямо от 1125. След това сме удебелили 25, 100, 200 и 800, защото 800+200+100+25 = 1125. Виждаме, че на тези числа отговарят 1, 4, 8 и 32. От тук получаваме, че търсеното 1125:25 = 32+8+4+1 = 45.

Делението с остатък се извършва по същия начин, но сбора от маркираните числа в дясната колона доближава максимално (отдолу) делимото, но не го достига напълно. Разликата между този сбор и делимото ще е остатъка.