Позиционни бройни системи. Двоична бройна система
от Българският сайт за математика
Понятието число е едно от най-важните в математиката. То е и едно от най-древните, които човечеството е изграждало в продължение на хилядолетия. При неговото развитие са се формирали понятия за естествено число, за дробно число и т.н. Практическите нужди на хората са наложили да се измислят различни правила за означаване и изговаряне на числата, за извършване на аритметичните операции. Възникнали са различни бройни системи. При приложението им са се оформяли и различни изисквания към тях, по-важните от които в наше време са следните:
1. Всяко число да има свое единствено значение.
2. Чрез прости правила означенията на всички числа да се образуват по еднообразен начин.
3. Използваните цифри да са удобни за изписване и изговаряне.
4. По възможност броят на цифрите да е малък.
5. Означенията на числата да са кратки.
6. Лесно да се определя означението на дадено число и обратно - по означението лесно да се разпознава числото.
7. Означенията на числата да са удобни за извършване на операциите броене, сравняване, събиране, изваждане и т.н.
8. Означаването на числата да е удобно за изпълнител машина.
Трябва да отбележим, че някои от изброените изисквания са противоречиви. Например, използването на по-малък брой цифри води до по-дълги означения на числата. Затова в съвременната изчислителна практика, според нуждите, се използват различни бройни системи.
При някои бройни системи стойността, която означава определена цифра, е винаги една и съща, като не зависи от позицията (мястото) което цифрата заема в означението на числото. Такива бройни системи се наричат непозиционни. В други - една и съща цифра, в зависимост от позицията която заема в означението на числото, означава различни стойности. Такива системи са наричат позиционни. Едно предимство на позиционните системи в сравнение с непозиционните е относително по-малкият брой цифри и по-лесното извършване на операциите.
Теоритично позиционните бройни системи се основават на следната теорема, която ще приемем без доказателство:
Всяко естествено число M може да се представи по единствен начин във вида:
където p е цяло число не по-малко от 2, n - цяло неотрицателно число и са цифри, означаващи цели неотрицателни числа, по-малки от p и
Съгласно тази теорема числото M, при фиксирано p, е напълно опредлено от цифрите , взети в посочения ред. Тъй като числото p играе в случая основна роля, то прието е поредицата от цифри
да служи за означение на числото M в p-ичната позиционна бройна система, т.е. дава се следното определение:
p-ична позиционна бройна система се нарича бройната система с p различни цифри 0, 1, 2,...., p-1, при която означението
представлява числото
Естественото число p се нарича основа на p-ичната бройна система.
При p = 10 имаме познатата десетична бройна система, с която в настоящия момент си служат всички културни народи. За да изразим, че едно число е записано в десетична бройна система, ще казваме накратко, че е десетично.
Условието е необходимо, защото в противен случай ще бъде нарушено първото изискване към бройните системи, т.е. всяко число ще има безброй означения. Например, означенията на числото 18 ще могат да бъдат 18, 018, 0018 и т.н.
В миналото някои народи са употребявали позиционни бройни системи с други основи. Тяхното влияние се е запазило и до сега. Например, основа 60 се използва в геометрията и астрономията, ъглите измерваме в градуси, минути и секунди, часовете - в минути и секунди.
При p = 2 се получава двоична позиционна бройна система. Едно сравнение на извършването на операциите при нея с това при десетичната бройна система показва, че в двоичната то е по-просто. Това се дължи на обстоятелството, че при нея (двоичната) се използват само две цифри - 0 и 1. При тези пресмятания в същност или запазваме дадена цифра, или я заменяме с другата възможна. Следователно отговаряме с "да" или "не" на върпоса дали да се постави примерно цифрата 1 на дадено място. Ако работим в десетична бройна система, това не може да се осъществи. При нея отговорът, че цифрата, която трябва да се запише на даденото място, примерно не е 1, дава недостатъчна информация за това коя от останалите девет цифри би трябвало да се запише на същото място.
От друга страна двете цифри 0 и 1 лесно могат да се представят само с две физически състояния - например, положителен или отрицателен електрически потенциал, включен или изключен електрически ключ и т.н. Тези качества на двоичната бройна система я правят особено удобна при работа със съвременна изчислителна техника.
В следващото наше изложение ще ограничим с разглеждането на някои въпроси, свързани с означението на естествените числа в двоична система и аритметичните операции със същите числа в тази система.
Двоичното означение на произволно естествено число има вида:
, където
са единици или нули и
Първите десет естествени числа, записани в двоична система, са следните:
}; 2 = 10_{(2)}; 3 = 11_{(2)}; 4 = 100_{(2)}; 5 = 101_{(2)}; 6 = 110_{(2)}; <br>
</pre>
<p>7 = 111_{(2)}; 8 = 1000_{(2)}; 9 = 1001_{(2)}; 10 = 1010_{(2)}.)
Нека M е произволно естествено число, записано в десетична бройна система. Поставяме си задачата да го запишем в двоична система.
Ако двоичният запис на M е
, то можем да запишем равенството:
или
 + b_0)
Последното равенство можем да запишем и така:
,
където
. От него и поради това, че
е цифра в двоичния запис на M, т.е.
, следва, че
, т.е.
 + b_1 = 2M_2 + b_1)
където
и
Следователно
е остатъкът от делението на
Като вземем предвид, че остатъците при делене с 2 са 0 или 1 в зависимост от това дали делимото е четно или нечетно число, то можем да дадем следното правило за преминаване от десетична в двоична бройна система.
Записваме десетичното число и под него пишем 0, ако е четно, и 1, ако е нечетно. До разглежданото число отдясно записваме цялата част на половината му и с нея постъпваме по същия начин - под нея пишем 0, ако е четно число, и 1, ако е нечетно. Продължаваме така, докато на първия ред се получи единица, под която също пишем единица. Получените единици и нули на втория ред, взети в обратен ред на получаването им, образуват двоичния запис на разглежданото число.
Примери:
а)
243 121 60 30 15 7 3 1 1 1 0 0 1 1 1 1
}.)
б)
280 140 70 35 17 8 4 2 1 0 0 0 1 1 0 0 0 1
}.)
Всяко естествено число, записано в двоична бройна система, може лесно да се запише в десетична бройна система или, както се казва, да се приведе в десетична система. За това е достатъчно да се вземе предвид общата формула за представяне на едно число в p-ичната система и да се положи p = 2.
Примери:
а)
} = 1.2^3 + 1.2^2 + 0.2^1 + 1.2^0 = 13)
б)
} = 1.2^5 + 1.2^4 + 0.2^3 + 1.2^2 + 1.2 + 0 = 54)
Тези пресмятания могат да се извършват по-удобно, като се приложи в обратен ред даденото по-горе съкратено правило за записване на десетично число в двоична бройна система. В него по известно делимо и делител 2 се определят частното и остатъкът. В обратното правило трябва по известни делител 2, частно и остатък да се определи делимото.
За тази цел на първия ред се записва двоичният запис на числото, т.е. получаваните остатъци при деленето на 2, като се започва от последния остатък. Под тях се възстановяват частните при същото делене (те се явяват делимо при следващото). Това се постига като се удвоява предищното частно от втория ред и се прибавя съответният остатък от първия ред. Тъй като последното частно при първото правило е 0 и не се записва, то при обратното правило под най-старшата цифра на двоичния запис се записва 2.0 + 1 = 1.
Примери:
а)
1 1 1 1 0 0 1 1 1 3 7 15 30 60 121 243Последователните пресмятания в този случай са следните: 2.1 + 1 = 3; 2.3 + 1 = 7; 2.7 + 1 = 15; 2.15 + 0 = 30; 2.30 + 0 = 60; 2.60 + 1 = 121; 2.121 + 1 = 243, т.е.
} = 243.)
б)
1 0 1 1 0 1 0 0 0 1 1 2 5 11 22 45 90 180 360 721В този пример пресмятанията са следните: 2.1 + 0 = 2; 2.2 + 1 = 5; 2.5 + 1 = 11; 2.11 + 0 = 22; 2.22 + 1 = 45; 2.45 + 0 = 90; 2.90 + 0 = 180; 2.180 + 0 = 360; 2.360 + 1 = 721.
Това правило е известно в математиката под името правило на Хорнер. В много случаи пресмятанията при него не могат да се извършват на ум.
Аритметичните операции (събиране, изваждане, умножение и делене) в двоична система се извършват по правилата, с които се работи в десетична система. Това ще илюстрираме с примери.
Събиране: Трябва да се има предвид, че две единици от определен разряд образуват една единица от следващия по-висок разряд. Очевидно ще имаме равенствата: 0 + 0 = 0; 0 + 1 = 1 + 0 = 1; 1 + 1 = 10. Тогава събирането на многозначни числа ще изглежда така:
а) 1011100101 б) 101101 + 10111100 + 11001 = 1110100001 = 1000110Ако събираемите са повече, то при някои разряди може да се окажат няколко единици за "пренасяне". В такива случаи е по-удобно вместо да ги "запазваме на ум", да ги записваме над съответните разряди. За да ги отделим от събираемите, над тях поставяме черта.
Примери:
а) 1 б) 111 1111 11111 11111111111 _________ _______________ 1101 10110011101 + 1011 1011101110 1001 + 110000101 _________ 1100111111 100001 _______________ 110101001111Изваждане: Да се има предвид, че 0 - 0 = 0; 1 - 0 = 1; 1 - 1 = 0; 10 - 1 = 1.
Примери:
... ...... ...... а) 1000 б) 1001000 в) 10101001011111 - 1 - 11001 - 111010010000 _______ _________ __________________ 111 101111 1101111001111Умножение: Тъй като произведението с множител нула е равно на нула, то таблицата за умножение в двоичната система се състои само от един ред - 1.1 = 1. Затова умножението на многозначни числа се свежда до "преместване" и събиране. За да бъдат събираемите по-малко на брой, трябва за втори множител да се вземе числото, чийто запис има по-малък брой единици. Когато получените събираеми са повече, за удобство, между тях и множителите се оставя място за записване на единиците за пренос.
Примери:
а) 11011 б) 111001101 . 1001 . 1110001 ____________ __________________ 11011 11 11 + 11011 111111111 ____________ __________________ 11110011 111001101 111001101 + 111001101 111001101 __________________ 1100101101111101Делене: Тъй като цифрите на частното са 0 и 1, не е необходимо да се умножава делителят. При нужда той само се преписва на подходящото място.
Примери:
а) 101000100 : 10010 б) 10101110001111 : 11011 - 10010 10010 - 11011 110011101 _____ _____ 10010 100001 - 10010 - 11011 _____ ______ 0 110000 - 11011 ______ 101011 - 11011 ______ 100001 - 11011 ______ 11011 - 11011 _____ 0Задачи:
1. Приведете числата 72, 85, 123, 218, 773 в двоична система.
2. Извършете означените операции. Приведете числата в десетична система и направете проверка.
а) 110101 б) 100111 в) 1101001101 г) 1101110 д) 101101 е) 110001 ж) 100010011 : 1011 + 11101 + 1010 - 11100110 - 101101 . 1101 . 11111 ________ 11101 ____________ _________ _______ ________ ________