Бройни системи


с. 1 с. 2

Глава 8. Бройни системи

[TODO:remove]Автор


Петър Велев

Светлин Наков


В тази тема...


В настоящата тема ще разгледаме начините на работата с различни бройни системи и представянето на числата в тях. Повече внимание ще отделим на представянето на числата в десетична, двоична и шестнаде­сетична бройна система, тъй като те се използват масово в компютърната техника и в програмирането. Ще обясним и начините за кодиране на числовите данни в компютъра и видовете кодове, а именно: прав код, обратен код, допълнителен код и двоично-десетичен код.

История в няколко реда


Използването на различни бройни системи е започнало още в дълбока древност. Това твърдение се доказва от обстоятелството, че още в Египет са използвани слънчевите часовници, а техните принципи за измерване на времето ползват бройни системи. По-голямата част от историците смятат древноегипетската цивилизация за първата цивилизация, която е разделила деня на по-малки части. Те постигат това, посредством употре­бата на първите в света слънчеви часовници, които не са нищо друго освен обикновени пръти, забити в земята и ориентирани по дължината и посоката на сянката.

По-късно е изобретен по-съвършен слънчев часовник, който прилича на буквата Т и е градуиран по начин, по който да разделя времето между изгрев и залез слънце на 12 части. Това доказва използването на двана­десетична бройна система в Египет, важността на числото 12 обикновено се свързва и с обстоятелството, че лунните цикли за една година са 12, или с броя на фалангите на пръстите на едната ръка (по три на всеки от четирите пръста, като не се смята палеца).

В днешно време десетичната бройна система е най-разпространената бройна система. Може би това се дължи на улесненията, които тя предо­ставя на човека, когато той брои с помощта на своите пръсти.

Древните цивилизации са разделили денонощието на по-малки части, като за целта са използвали различни бройни системи, дванадесетични и шестдесетични съответно с основи – 12 и 60. Гръцки астрономи като Хипарх са използвали астрономични подходи, които преди това са били използвани и от вавилонците в Месопотамия. Вавилонците извършвали астрономич­ните изчисления в шестдесетична система, която били насле­дили от шумерите, а те от своя страна да я развили около 2000 г. пр. н. е. Не е известно от какви съображения е избрано точно числото 60 за основа на бройната система, но е важно да се знае че, тази система е много подходяща за представяне на дроби, тъй като числото 60 е най-малкото число, което се дели без остатък съответно на 1, 2, 3, 4, 5, 6, 10, 12, 15, 20 и 30. 


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


Днес шестдесетичната система все още се използва за измерване на ъгли, географски координати и време. Те все още намират приложение при часовниковия циферблат и сферата на глобуса. Шестдесетичната бройна система е използвана и от Ератостен за разделянето на окръжността на 60 части с цел създаване на една ранна система от географски ширини, съставена от хоризонтални линии, минаващи през известни в миналото места от земята. Един век след Ератостен Хипарх нормирал тези линии, като за целта ги направил успоредни и съобразени с геометрията на Земята. Той въвежда система от линии на географската дължина, в които включват 360 градуса и съответно минават от север до юг и от полюс до полюс. В книгата "Алмагест" (150 г. от н. е.) Клавдий Птолемей доразвива разработките на Хипарх чрез допълнително разделяне на 360-те градуса на географската ширина и дължина на други по-малки части. Той разделил всеки един от градусите на 60 равни части, като всяка една от тези части в последствие била разделена на нови 60 по-малки части, които също били равни. Така получените при деленето части, били наречени partes minutae primae, или "първа минута" и съответно partes minutae secundae, или "втора минута". Тези части се ползват и днес и се наричат съответно "минути" и "секунди".

Кратко обобщение


Направихме кратка историческа разходка през хилядолетията, от която научаваме, че бройните системи са били създадени, използвани и развивани още по времето на шумерите. От изложените факти става ясно защо денонощието съдържа (само) 24 часа, часът съдържа 60 минути, а минутата 60 секунди. Това се дължи на факта, че древните египтяни са разделили по такъв начин денонощието, като са въвели употребата на дванадесетична бройна система. Разделянето на часовете и минутите на 60 равни части, е следствие от работата на древногръцките астрономи, които извършват изчисленията в шестдесетична бройна система, която е създадена от шумерите и използвана от вавилонците.

Бройни системи


До момента разгледахме историята на бройните системи. Нека сега разгледаме какво представляват те и каква е тяхната роля в изчислител­ната техника.

Какво представляват бройните системи?


Бройните системи са начин за представяне (записване) на числата, чрез краен набор от графични знаци наречени цифри. Към тях трябва да се добавят и правила за представяне на числата. Символите, които се използват при представянето на числата в дадена бройна система, могат да се възприемат като нейна азбука.

По време на различните етапи от развитието на човечеството, различни бройни системи са придобивали известност. Трябва да се отбележи, че днес най-широко разпространение е получила арабската бройна система. Тя използва цифрите 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9, като своя азбука. (Интересен е фактът, че изписването на арабските цифри в днешно време се различава от представените по-горе десет цифри, но въпреки това, те пак се отнасят за същата бройна система т.е. десетичната).

Освен азбука, всяка бройна система има и основа. Основата е число, равно на броя различни цифри, използвани от системата за записване на числата в нея. Например арабската бройна система е десетична, защото има 10 цифри. За основа може да се избере произволно число, чиято абсолютна стойност трябва да бъде различна от 0 и 1. Тя може да бъде и реално или комплексно число със знак.

В практическо отношение, възниква въпросът: коя е най-добрата бройна система, която трябва да използваме? За да си отговорим на този въпрос, трябва да решим, как ще се представи по оптимален начин едно число като записване (т.е. брой на цифрите в числото) и брой на цифрите, които използва съответната бройна система т.е. нейната основа. По математи­чески път, може да се докаже, че най-доброто съотношение между дължи­ната на записа и броя на използваните цифри, се постига при основа на бройната система Неперовото число (e = 2,718281828), което е основата на естествените логаритми. Да се работи в система с тази основа, е изключително неудобно, защото това число не може да се представи като отношение на две цели числа. Това ни дава основание да заключим, че оптималната основа на бройната система е 2 или 3. Въпреки, че 3 е по-близо до Неперовото число, то е неподходящо за техническа реализация. Поради тази причина, двоичната бройна система, е единствената подхо­дяща за практическа употреба и тя се използва в съвременните елек­тронноизчислителни машини.


Позиционни бройни системи


Бройните системи се наричат позиционни, тогава, когато мястото (пози­цията) на цифрите има значение за стойността на числото. Това означава, че стойността на цифрата в числото не е строго определена и зависи от това на коя позиция се намира съответната цифра в дадено число. Например в числото 351 цифрата 1 има стойност 1, докато при числото 1024 тя има стойност 1000. Трябва да се отбележи, че основите на бройните системи се прилагат само при позиционните бройни системи. В позиционна бройна система числото A(p) = (a(n)a(n-1)...a(0),a(-1)a(-2)...a(-k)) може де се представи във вида:

В тази сума Tm има значение на теглови коефициент за m-тия разряд на числото. В повечето случаи обикновено Tm = Pm, което означава, че



Образувано по горната сума, числото A(p) е съставено съответно от цяла си част (a(n)a(n-1)...a(0)) и от дробна си част (a(-1)a(-2)...a(-k)), където всяко a принадлежи на множеството от цели числа M={0, 1, 2, ..., p-1}. Лесно се вижда, че, при позиционните бройни системи стойността на всеки разряд е по-голяма от стойността на предходния разряд (съседния разряд отдясно, който е по-младши) с толкова пъти, колкото е основата на бройната система. Това обстоятелство, налага при събиране да прибавяме единица към левия (по-старшия) разряд, ако трябва да представим цифра в текущия разряд, която е по-голяма от основата. Системите с основи 2, 8, 10 и 16 са полу­чили по-широко разпространение в изчислителната техника, и в следва­щата таблица е показано съответното представяне на числата от 0 до 15 в тях:



Двоична

Осмична

Десетична

Шестнадесетична

0000

0

0

0

0001

1

1

1

0010

2

2

2

0011

3

3

3

0100

4

4

4

0101

5

5

5

0110

6

6

6

0111

7

7

7

1000

10

8

8

1001

11

9

9

1010

12

10

A

1011

13

11

B

1100

14

12

C

1101

15

13

D

1110

16

14

E

1111

17

15

F

[TODO: http://en.wikipedia.org/wiki/Octal - give an example, how to convert these values. Give for example one row.]

Непозиционни бройни системи


Освен позиционни, съществуват и непозиционни бройни системи, при които стойността на всяка цифра е постоянна и не зависи по никакъв начин от нейното място в числото. Като примери за такива бройни системи могат да се посочат съответно римската, гръцката, милетската и др. Като основен недостатък, на непозиционните бройни системи трябва да се посочи това, че чрез тях големите числа се представят неефективно. Заради този си недостатък те са получили по-ограничена употреба. Често това би могло да бъде източник на грешка при определяне на стойността на числата. Съвсем накратко ще разгледаме римската и гръцката бройни системи.

Римска бройна система


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

Римска цифра

Десетична равностойност

I

1

V

5

X

10

L

50

C

100

D

500

М

1000

Както вече споменахме, в тази бройна система позицията на цифрата не е от значение за стойността на числото, но за нейното определяне се прилагат следните правила:

[TODO: Clarify the examples below, they are too ‘look this is obvious’]


  1. Ако две последователно записани римски цифри, са записани така, че стойността на първата е по-голяма или равна на стойността на втората, то техните стойности се събират. Пример:

Числото III=3, а числото MMD=2500.

  1. Ако две последователно записани римски цифри, са в намаляващ ред на стойностите им, то техните стойности се изваждат. Пример:

Числото IX=9, числото XML=1040, а числото MXXIV=1024.

Гръцка бройна система


Гръцката бройна система, е десетична система, при която се извършва групиране по петици. Тя използва следните цифри:

Гръцка цифра

Десетична равностойност

Ι

1

Π

5

Δ

10

Η

100

Χ

1 000

Μ

10 000

Следват примери на числа от тази система:

[TODO: Again, clarify the examples, it’s again ‘it’s too obvious’ ]
ΓΔ = 50, ΓH = 500, ΓX = 5000, ΓM = 50 000.

Двоичната бройна система – основа на електронноизчислителната техника


Двоичната бройна система, е системата, която се използва за представяне и обработка на числата в съвременните електронноизчислителни машини. Главната причина, поради която тя се е наложила толкова широко, се обяснява с обстоятелството, че устройства с две устойчиви състояния се реализират просто, а разходите за производство на двоични аритметични устройства са много ниски.

Двоичните цифри 0 и 1 лесно се представят в изчислителната техника като "има ток" / "няма ток" или като "+5V" и "-5V".

Наред със своите пре­димства, двоичната система за представяне на числата в компютъра си има и недостатъци. Един от големите практически недоста­тъци, е, че числата, представени с помощта на тази система са много дълги, т. е. имат голям брой разреди (битове). Това я прави неудобна за непосредствена употреба от човека. За избягване на това неудобство, в практиката се ползват бройни системи с по-големи основи.

Десетични числа


Числата представени в десетична бройна система, се задават в първичен вид т.е. вид удобен за възприемане от човека. Тази бройна система има за основа числото 10. Числата записани в нея са подредени по степените на числото 10. Младшият разряд (първият отдясно на ляво) на десетичните числа се използва за представяне на единиците (100=1), следващият за десетиците (101=10), следващият за стотиците (102=100) и т.н. Казано с други думи, всеки следващ разряд е десет пъти по-голям от предшест­ващия го разряд. Сумата от отделните разряди определя стойността на числото. За пример ще вземем числото 95031, което в десетична бройна система се представя като:

95031 = (9x104) + (5x103) + (0x102) + (3x101) + (1x100)

Представено в този вид, числото 95031 е записано по естествен за човека начин, защото принципите на десетичната система са възприети като фун­даментални за хората. [TODO: Kato e vajno, da se dobavi vyv [Vajno] kare] Много е важно да се отбележи, че тези подходи важат и за останалите бройни системи. Те имат същата логическа поста­новка, но тя е приложена за бройна система с друга основа. Последното твърдение, се отнася включително и за двоичната и шестнайсетината бройни системи, които ще разгледаме в детайли след малко.

Двоични числа


Числата представени в тази бройна система, се задават във вторичен вид т.е. вид удобен за възприемане от изчислителната машина. Този вид е малко по-трудно разбираем за човека. За представянето на двоичните числа, се използва двоичната бройна система, която има за основа числото 2. Числата записани в нея са подредени по степените на двойката. За тяхното представяне, се използват само цифрите 0 и 1.

Прието е, когато едно число се записва в бройна система, различна от десетичната, във вид на индекс в долната му част да се отразява, коя бройна система е използвана за представянето му. Например със записа 1110(2) означаваме число в двоична бройна система. Ако не бъде указана изрично, бройната система се приема, че е десетична. Числото се произ­нася, като се прочетат последователно неговите цифри, започвайки от ляво на дясно (т.е. прочитаме го от старшия към младия разряд "бит").

Както и при десетичните числа, гледано от дясно наляво, всяко двоично число изразява степените на числото 2 в съответната последователност. На младшата позиция в двоично число съответства нулевата степен (20=1), на втората позиция съответства първа степен (21=2), на третата позиция съответства втора степен (22=4) и т.н. Ако числото е 8-битово, степените достигат до седма (27=128). Ако числото е 16-битово, степените достигат до петнадесета (215=32768). Чрез 8 двоични цифри (0 или 1) могат да се представят общо 256 числа, защото 28=256. Чрез 16 двоични цифри могат да се представят общо 65536 числа, защото 216=65536.

Нека даден един пример за числа в двоична бройна система. Да вземем десетичното число 148. То е съставено от три цифри: 1, 4 и 8, и съответства на следното двоично число:



10010100(2)

148 = (1x27) + (1x24) + (1x22)

Пълното представяне на това число е изобразено в следващата таблица:



Число

1

0

0

1

0

1

0

0

Степен

27

26

25

24

23

22

21

20

Стойност

1x27=128

0x26=0

0x25=0

1x24=16

0x23=0

1x22=4

0x21=0

0x20=0

Последователността от осем на брой нули и единици представлява един байт, т.е. това е едно обикновено осем-разредно двоично число. Чрез един байт могат да се запишат всички числа от 0 до 255 включи­телно. Много често това е не достатъчно и затова се използват по няколко последователни байта за представянето на едно число. Два байта образуват т.н. "машинна дума" (word), която отговаря на 16 бита (при 16-разредните изчислителни машини). Освен нея, в изчислителните машини се използва и т.н. "двойна дума" (double word) или (dword), съответстваща на 32 бита.



Ако едно двоично число завършва на 0, то е четно, а ако завършва на 1, то е нечетно.

Преминаване от двоична в десетична бройна система


При преминаване от двоична в десетична бройна система, се извършва преобразуване на двоичното число в десетично. Всяко число може да се преобразува от една бройна система в друга, като за целта се извършат последователност от действия, които са възможни и в двете бройни системи. Както вече споменахме, числата записани в двоична бройна система се състоят от двоични цифри, които са подредени по степените на двойката. Нека да вземем за пример числото 11001(2). Преобразуването му в десетично се извършва чрез пресмятането на следната сума:

11001(2) = 1x24 + 1x23 + 0x22 + 0x21 + 1x20 =

= 16(10) + 8(10) + 1(10) = 25(10)

От това следва, че 11001(2) = 25(10)

С други думи, всяка една двоична цифра се умножава по 2 на степен, позицията, на която се намира (в двоичното число). Накрая се извършва събиране, на числата, получени за всяка от двоичните цифри, за да се получи десетичната равностойност на двоичното число.



[TODO: Da se preraboti, da se dade malko formulate na Horner I t.n. ..]
Съществува и още един начин за преобразуване, който е известен като схема на Хорнер. При тази схема се извършва умножение на най-лявата цифра по две и събиране със съседната й вдясно. Този резултат се умножава по две и се прибавя следващата съседна цифра от числото (цифрата вдясно). Това продължава до изчерпване на всички цифри в числото, като последната цифра от числото се добавя без умножаване. Ето един пример:

1001(2) = ((1.2+0).2+0).2+1 = 2.2.2+1 = 9

Преминаване от десетична към двоична бройна система


При преминаване от десетична в двоична бройна система, се извършва преобразуване на десетичното число в двоично. За целите на преобразу­ването се извършва делене на две с остатък. Така се получават частно и остатък, който се отделя.

Отново ще вземем за пример числото 148. То се дели целочислено на основата, към която ще преобразуваме (в примера тя е 2). След това, от остатъците получени при деленето (те са само нули и единици), се записва преобразуваното число. Деленето продължава, докато получим частно нула. Ето пример:

148:2=74 имаме остатък 0;

74:2=37 имаме остатък 0;

37:2=18 имаме остатък 1;

18:2=9 имаме остатък 0;

9:2=4 имаме остатък 1;

4:2=2 имаме остатък 0;

2:2=1 имаме остатък 0;

1:2=0 имаме остатък 1;

След като вече семе извършили деленето, записваме стойностите на остатъците в ред, обратен на тяхното получаване, както следва:

10010100


т.е. 148(10) = 10010100 (2)

[TODO: Primerat otdolu, da obiasni algoritamat za generiraneto na tezi cifri I da se dobavi kod na C# za prehvyrlianeto na chislo ot 10-chna v 2-chna broina sistema. Moje bi nai-otdolu na glavata, triabva da se dade I algoritam+kod za prehvyrliane ot vsiakakva kym vsiakakva druga sistema]

[TODO: kod za algoritamat na C#, izpolzvaiki pobitovi operacii???]

[TODO: Da se dobavi sekcia, za ‘efektivna’ rabota sys dvoichni chisla… moje da se izpolzva statiata ot wiki-to za algoritmite, tam ima statia za dvoichnite chisla I pobitovite operacii v C++]

[TODO: Da se dobavi sekcia za pobitovite operacii]

Действия с двоични числа


При двоичните числа за един двоичен разряд са в сила аритметичните правила за събиране, изваждане и умножение.

0+0=0 0-0=0 0.0=0

1+0=1 1-0=1 1.0=0

0+1=1 1-1=0 0.1=0

1+1=10 10-1=1 1.1=1

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

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

Шестнайсетични числа


При тези числа имаме за основа на бройната система числото 16, което налага да бъдат използвани 16 знака (цифри) за представянето на всички възможни стойности от 0 до 15 включително. Както вече беше показано в една от таблиците в предходните точки, за представянето на шестнайсе­тичните числа се използват числата от 0 до 9 и латинските букви от A до F. Всяка от тях има съответната стойност:

A=10, B=11, C=12, D=13, E=14, F=15

Като примери за шестнайсетични числа могат да бъдат посочени съответно, D2, 1F2 F1, D1E и др.

Преминаването към десетична система става като се умножи по 160 стойността на най-дясната цифра, по 161 следващата вляво, по 162 следващата вляво и т.н. и накрая се съберат. Например:

D1E(16) = Е*160 + 1*161 + D*162 = 14*1 + 1*16 + 13*256 = 3358(10).

Преминаването от десетична към шестнайсетична бройна система става като се дели десетичното число на 16 и се вземат остатъчите в обратен ред. Например:

3358 / 16 = 209 + остатък 14 (Е)

209 / 16 = 13 + остатък 1 (1)

13 / 16 = 0 + остатък 13 (D)

Взимаме остатъците в обратен ред и получаваме числото D1E(16).


Бързо преминаване от двоични към шестнайсетични числа


Бързото преобразуване, от двоични в шестнайсетични числа се извършва бързо и лесно, чрез разделяне на двоичното число на групи от по четири бита (разделяне на полубайтове). Ако броят на цифрите в числото не е кратен на четири, то се добавят водещи нули в старшите разреди. След разделянето и евентуалното добавяне на нули, се заместват всички полу­чени групи със съответстващите им цифри. Ето един пример:

Нека да ни е дадено следното число: 1110011110(2).



  1. Разделяме го на полубайтове и добавяме водещи нули

Пример: 0011 1001 1110.

  1. Заместваме всеки полубайт със съответната шестнайсетична цифра и така получаваме 39E(16).

Следователно 1110011110 (2) = 39E(16).

с. 1 с. 2

скачать файл