C, PHP, VB, .NET

Защо след като в ежедневния си живот извършваме сметки с десетични числа, компютрите в днешно време използват само двоични? Причините са от чисто физичен характер. Както знаем се използват електрически сигнали. Представете си, че имаме един датчик, който трябва да отчита такъв сигнал. Сравнително лесно е да се направи датчик, който отчита дали има (1) или няма ток (0). Реално не се интересуваме от характеристиките на сигнала - няма значение дали е силен или слаб, защото единственото, което е важно за нас, е дали го има или го няма. Ако искаме от същия сигнал да представим троична, или още по-трудно - нашата добре позната десетична - бройна система, ще трябва да отчитаме някакви допълнителни качества на сигнала - например неговата сила. Да, но това прави "датчикът" много по-сложен - започваме да се нуждаем от много по-чист сигнал, защото евентуални смущения ще водят до появата на грешни отчитания. Като добавим това, че в процесора на един съвременен компютър са необходими над 1 милиард и 200 милиона такива датчици (всъщност се наричат превключватели или още по-точно транзистори), това прави (поне на този етап) двоичната бройна система единствен адекватен избор. Именно простотата на двоичната бройна система я е наложила - тя позволява да се използват елементарни превключватели, наречени "транзистори", които са изключително миниатюрни и може да се слагат по много в много малки физически обеми.

Има и още едно съображение за употребата на двоична бройна система - икономичността при запис на информацията. Ако разгледаме числото 185₁₀ например и го съпоставим с неговото двоично представяне 10111001₂ ни се струва, че двоичното заема повече място. Това обаче е само визуална заблуда, защото за да отделим място за запис на десетичното число ни трябват 3 цифри от 10 възможни или общо 30 възможни комбинации. При двоичното имаме 8 цифри по 2 възможни или общо 16 възможни комбинации, т.е. ще заемат почти двойно по-малко пространство. По същият начин числото 999999₁₀ заема 6 цифри по 10 възможни или ни е нужно пространство за 60 възможни комбинации, а неговото двоично представяне 11110100001000111111₂ има 20 цифри по 2 възможни или оценката за ефективност е 40 възможни комбинации. Всъщност от математическа гледна точка, най-ефективна е троичната бройна система, като двоичната я следва сравнително близко по ефективност. В крайна сметка двоичната бройна система категорично печели битката спрямо десетичната именно защото едновременно се изискват се много по-евтини и по-прости хардуерни компоненти и е по-икономична - заема се по-малко пространство за запис на числата.

Сега остава да си обясним как точно се записват тези числа. В предишната статия показахме как се превръщат цели положителни десетични числа в двоични. Логично е да приемем, че компютъра ги запазва точно по този начин - в огромно количество различни "клетки памет" (RAM, твърд диск, флаш памет и др), които от сега нататък ще наричаме "битове", ще се пази информация дали има или няма сигнал. Така едно двоично число ще се представи като последователност от съседни записи в такива клетки, т.е. поредица от битове. Как обаче да определим къде свършва едно число и къде започва друго? Например последователността от битове 11011010 може да представя както числата 1101₂ и 1010₂, така и числата 110110₂ и 10₂, както и всякакви други комбинации в зависимост къде разделим числото на две, три или повече части. Поради тази причина виждаме, че по естествен път идва нуждата от това да определяме групи от клетки, всяка от които да съдържа в себе си по няколко бита и тези клетки да са с фиксирана дължина. С други думи определяйки такива клетки ние ще знаем откъде започва и къде свършва дадено число. Ако сме отделили повече пространство за едно число, просто ще запълваме битовете му наляво с 0-ли. И понеже смятаме с двоична бройна система, най-естествения избор за това е да използваме блокове от клетки, които са с брой битове степени на двойката:

• 1 клетка памет ще наричаме бит;
• 8 клетки памет (2³ бита) ще наричаме байт;
• 1024 клетки памет (2¹⁰ бита или 1024 байта) ще наричаме кибибайт;
• 1024² клетки памет (2²⁰ бита или 1024 кибибайта) ще наричаме мебибайт;
• 1024³ клетки памет (2³⁰ бита или 1024 мебибайта) ще наричаме гибибайт;
• 1024⁴ клетки памет (2⁴⁰ бита или 1024 гибибайта) ще наричаме тебибайт.

Веднага се досещаме, че компютърът няма безкрайно количество памет - то е ограничено физически. Тоест ние няма как да запишем произволно големи цели числа - винаги ще съществува някакво ограничение в зависимост от колко памет разполагаме. За щастие ние в ежедневието си боравим с не особено големи числа. Затова в програмирането, в зависимост от езика за програмиране който използвате разбира се, са наложени определени стандарти за т.нар. "примитивни типове данни", т.е. кой видове числа колко клетки памет да заемат. За програмният език Java за целите числа това са:

• byte - един байт;
• short - два байта;
• int - четири байта;
• long - осем байта.

В зависимост от броя клетки можете и лесно да пресметнете кое е най-голямото число, което съответен тип данни може да побере. Но почакайте, какво правим например с отрицателните числа? Някои езици за програмиране позволяват тип данни да е signed (със знак) или unsigned (без знак), а други (като Java) не - там всички са signed. Как обаче те записват знакът "-" чрез битове?

И още нещо - можем ли да записваме двоичните числа по различен начин, така че на компютъра да му е по-лесно да извършва сметки с тях?

Има четири наложили се стандарти за запис на двоични числа при компютрите. Те в известна степен се различават от това, което на хората им е интуитивно и лесно, когато пишат двоични числа на хартия (както го правихме досега), и поради тази причина вече ще ги наричаме с ново име: "бинарни числа". Бинарното число е просто начин за запазване на двоично число на компютър.

Signed Magnitude - бинарни числа със знаков бит:

Използва се най-левият бит на числото (нарича се "most significant bit" - най-старши бит) за определяне на знака на числото. Ако този бит е 0, приемаме числото за положително, а ако е 1, приемаме го за отрицателно. Например:

• 00001101 - числото +0001101₂ или +13₁₀
• 10001101 - числото -0001101₂ или -13₁₀

Това представяне е много просто и лесно разбираемо за хората, но е недостатъчно ефективно за компютрите, когато трябва да извършват операцията "изваждане" - тук машинно тя е по същество различна от събирането, защото вместо пренасяне на битове наляво с "едно наум" (когато имаме 1+1) имаме пренасяне надясно с "едно назаем" (при 0-1). Между другото забележете, че можем да имаме две различни преставяния на числото 0 - може да е положителна или отрицателна 0. И двете се приемат естествено за 0, но това разбира се води до някакви неудобства.

One's complement - бинарни числа със знаков бит и инвертиране на цифрите

Отново най-левия (най-старшия) бит определя знака. Това, което прави различно това представяне обаче е инверсията (обръщането на всички битове наобратно) при отрицателните числа. Положителните са същите както в предишния тип. Тоест:

• 00001101 - числото +0001101₂ или +13₁₀
• 11110010 - числото е -1110010_2oc, неговото инверсно е -0001101₂ или това дава -13₁₀

Позитивното при този вид бинарни числа е фактът, че събирането и изваждането стават една и съща операция, което облекчава дизайнът и реализацията на  ALU (arithmetic logical unit, т.е. аритметичния логически модул на централния процесор на компютъра). Нека дадем един пример - искаме да пресметнем 17-9 = 17+(-9). Първо определяме бинарния вид в "oc" вариант:

17₁₀ = 00010001_2oc
-9₁₀ = 11110110_2oc

Сега ги събираме:

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

Нарочно удебелихме най-лявата цифра (старшия бит) от това събиране - тя излиза извън типа на данните (ние работим с бинарни числа от 8 бита, а резултата стана 9 битов). Когато това се случи, премахваме тази цифра и извършваме второ събиране, този път с числото 1. Казано с други думи премахваме старшия бит от края на числото ако е излезнал извън границите на типа и го добавяме към новото число:

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

Видяхме, че резултатът от 17₁₀-9₁₀ = ... = 00001000_2oc = 8₁₀, което естествено е верен резултат.

Веднага можете да си зададете въпроса "а какво става ако събираме две положителни числа и те надхвърлят границите на типа"? Отговорът е смущаващ, но според тези правила ще се получи отрицателно число. Това се нарича "прехвърляне на типа" (integer overflow) и често е причинител на неприятни грешки в компютърните програми.

Виждаме, че спрямо предишния вариант имаме едно голямо подобрение - вече операцията събиране и операцията изваждане от ежедневния живот се сведоха до една единствена компютърна операция - събиране. Схемата one's complement обаче не е много разпространена при изчислителната техника. Причината за това е, че тук отново имаме проблема с двете нули - имаме както положителна, така и отрицателна нула.

Two's complement - бинарни числа със знаков бит и инвертиране на цифрите с добавена единица

В предишния тип бинарни числа при операцията изваждане винаги премахваме най-старшия бит и го добавяме към резултатното число. В two's complement схемата ние предварително добавяме този бит и пазим отрицателните числа с него. С други думи едно two's complement число е one's complement число с добавено 1.

Нека отново изчислим 17-9, този път в този бинарен вид.

17₁₀ = 00010001₂ = 00010001_2oc = 00010001_2tc - положителните числа и в трите форми са едни и същи
- 9₁₀ = 10001001₂ = 11110110_2oc = 11110111_2tc - tc е просто oc с добавена единица

Сега събираме тези две числа:

[math]\begin{matrix}
&0&0&0&1&0&0&0&1\\
+&1&1&1&1&0&1&1&1\\
\hline
\require{enclose}
\enclose{horizontalstrike}{1}&0&0&0&0&1&0&0&0
\end{matrix}[/math]

Както виждате тук просто сме задраскали старшия бит, който излезе извън размера на типа. Ние сме го добавили предварително към отрицателното число и затова в този случай старшия бит просто отпада. Или казано по друг начин, one's и two's complement записването на две бинарни числа води до абсолютно аналогични действия, но в различна поредност. Това, което печелим тук обаче е, че вече нямаме две нули - единствено числото 0...0 е нула. Това е и причината повечето производители на процесори да са възприели използват именно тази форма на представяне на числата, откъдето и повечето езици за програмиране използват именно нея.

Един много лесен начин за намиране на two's complement формата на едно число е следният - тръгнете от дясно-налява по битовете в числото и намерете първата единица. Задръжте я такава, каквато си е, а останалите числа наляво ги инвертирайте.

Еndianness - посока на запис на данните

Можем да групираме поредните битове от паметта в байтове и да ги номерираме започвайки от 0, 1, 2, 3 и т.н. - така най-просто можем да приемем, че всеки един байт в паметта ще си има свой собствен индекс, който ще наричаме "адрес".

Когато обаче едно цяло число (а и не само, ние можем да записваме и други типове данни, както ще видим по-нататък) трябва да заеме например 32 бита или 4 байта (тип int), то ще трябва да се разположи не в един, а в четири адреса в паметта. Те естествено са последователни (един след друг). От тук нататък има още една важна характеристика при запазването не само на числа, а на данни попринцип: т.нар. "endianness". Дали да записваме числата в отделните байтове от ляво-надясно (по-младшите байтове към по-голямите адреси) или наобратно (по-младшите байтове към по-малките адреси)? Първото се нарича "big endian" (започваме да записваме от старшите байтове и завършваме се с с младшите байтове), а второто "little endian" (завършва се със старшите байтове). Забележете, че говоря за "младши байт" и "старши байт", а не бит!

Например ако имаме следното четирибайтовото число:

11111111000011111111000001010101

Неговите байтове са (подредени от най-старши към най-младши): (11111111), (00001111), (11110000) и (01010101).

Ако наименоваме байтовете с буквите A, B, C и D, то двата приети стандарта за подреждане в паметта са следните:

• Big endian: ABCD, или (11111111)(00001111)(11110000)(01010101)
• Little endian: DCBA, или (01010101)(11110000)(00001111)(11111111)

Казано по-просто - big endian е естествената последователност на записване на числата така, както хората ги записват на хартия, а при little endian записът "размества наобратно" техните байтове.

Първоначално ни се струва, че little endian няма особена логика и смисъл. При това той създава проблеми при преноса на информация. Представете си, че имаме два различни компютъра - един работещ по единия стандарт и друг, работещ по другия. Ако единият компютър запише това 32 битово число на някакъв носител с памет, след което пренесем този носител на другия компютър, това число ще бъде разчетено от втория като съвсем различно! По същият начин ако изпращаме данни по интернет с един вид endianness, а от другата страна ги приемат за другия, това отново ще предизвика проблем. Защо тогава не е приет стандарт - например по-логичния от гледна точка на реалния свят big endian?

Наименованието "little" и "big endian" идва от книгата за пътешествията на Гъливер. Там има история как половината от лилипутите обичали да чупят яйцата започвайки от острата част (the little end), а другите от дебелата част (the big end), което в крайна сметка прерастнало в конфликт и война. Така и при компютрите - всички са се разбрали какво е байт и как се нареждат битовете в него, разбрали са се и какво е int и че е от 4 байта, но от там нататък имат различен стандарт за това как да се подреждат отделните байтове на този int и съответно как да бъдат прочетени и наредени, за да бъде възстановен в десетично число и подаден на потребителя.

Защо съществуват тези два различни стандарта, кому е нужен този little endian, който ни обърква? Отговорът на този въпрос е, че и двата стандарта имат предимства и недостатъци спрямо оптимизацията - повече бързина на обработка на информацията при едни операции и по-малко при други. Когато се обръщаме към данните в паметта, ние използваме едни специални типове данни, наречени "указатели". В указателят сме записали адреса на първия байт в паметта, където стоят нашите данни, както и информация за това от кой тип са те. Ако кажем "адрес 1052 от тип int", ние знаем точно откъде започват данните, както и че са четири байта (защото са int) - тоест нашето число е разположено на адреси 1052, 1053, 1054 и 1055.

Е, представете си сега, че трябва да намерим дали едно число е четно или нечетно. Little endian машината очевидно ще има предимство - тя има указател директно към "младшия байт" на нашето число, защото той е разположен в адрес 1052 от примера, а указателят ни "сочи" точно натам. Тази машина ще прочете само този байт и веднага ще провери дали завършва на 1 или 0, т.е. дали е четен или нечетен (а това определя четността или нечетността на цялото число). При big endian положението не е такова - ние имаме адреса "p", но той е към старшия байт - по него няма как да се определи четност или нечетност. Трябва да добавим числото 3 към адреса, който имаме, за да намерим младшия байт, а това е една допълнителна операция - събиране.

Друго по-сериозно предимство на little endian е, че може много лесно да се разширяват (конвертират) типовете от данни - нека например имаме двубайтовото число (01010101)(11110000). То може много лесно да се разшири до четири байтово като просто добавим два нулеви байта в неговия край: (01010101)(11110000)(00000000)(00000000). Така ние не местим данните в паметта, а само добавяме новите. При big endian не е така.

Още едно предимство за little endian е това, че математическите операции за събиране стандартно се извършват от младшите към старшите битове. Тоест събираме битовете точно както ние събираме пишейки на хартия - отдясно-наляво. Това и естествения ред на прочитане на информацията при тази операция е точно такъв. При big endian трябва да отидем в края на числото и чак тогава да започнем да се връщаме назад, за да събираме или умножаваме.

Предимството на big endian? Основното е, че на нас - хората - ни е по-лесно да го четем по този начин. Това, което евентуално трябва да знаем, е че персоналните компютри, които използваме за ежедневна употреба - тези базирани на архиктектурите на Intel x86-64 или AMD64 - използват little endian. Big endian процесорите не са много и се срещат по-скоро при специализирана техника. Има и такива, като например широкоразпространените съвремени ARM процесори за мобилни устройства, които са "bi-endian", т.е. поддържат и двата стандарта.

Това, което е хубаво за нас е, че библиотеките на различните езици за програмиране отчитат този endianness от файловите формати и при нужда автоматично обръщат байтовете. Ако ние трябва сами да създаваме такъв файлов формат, най-простият начин за решение на проблема е да се записва вътре във файла чрез метаданни (например при текстовите файлове това е прието да е BOM - byte order mark). Така един и същи файл ще може да се чете от различни системи без проблем, защото те ще знаят как са подредени данните в него.

Заключение

В програмирането ние използваме най-често десетични числа. Например извършваме аритметични операции като:

int x = 10;
int y = (x-3)*8;

Това, което трябва да знаем, е че "зад кулисите" се случват операции по превръщане на подадените от нас числа в бинарен вид. Освен това трябва да помним, че числата, които записваме, заемат повече памет, отколкото обикновено им е нужно (заради нуждата от блокове на примитивните типове). Когато четем обратно резултата (например със System.out.println в Java), числото се превръща отново за нас в десетичен вид. Това е работа, която компилаторите вършат автоматично за нас - удобство, което ни кара да смятаме бързо и лесно с познатите ни десетични числа, без да мислим за бинарното им представяне. Подобно е положението и за endianness - ще ни се налага рядко да мислим за него ако работим с езици за програмиране от високо ниво.