Системи числення з довільною основою

Двійкова арифметика

 

Арифметичні дії в двійковій системі (двійковій арифметиці) виконуються за звичайними для позиційних систем правилами (алгоритмами), які нам відомі з десяткової арифметики, але при цьому, звичайно, використовуються таблиці додавання і множення двійкової системи.

Таблиця додавання

 

0+0=0

0+1=1

1+0=1

1+1=10₂

 

(додавання нуля не міняє числа, а один плюс один буде два).

Таблиця множення

0∙0=0

0∙1=0

1∙0=0

1∙1=1

(число, помножене на нуль, є нуль; множення на один не міняє числа).

Додавання. Додавання багатозначних чисел відбувається так само, як і в десятковій системі, тобто порозрядно, починаючи з молодшого.

 

101101₂ - 1 доданок

+ 10100₂ - 2 доданок

1000001₂ - сума

 

Перевіримо правильність наших обчислень:

101101₂=1∙2⁵+0∙2⁴+1∙2³+1∙2²+0∙2¹+1∙2⁰=32+0+8+4+0+1=45₁₀

10100₂=1∙2⁴+0∙2³+1∙2²+0∙2¹+0∙2⁰=16+0+4+0+0=20₁₀

45₁₀+20₁₀=65₁₀

1000001₂=1∙2⁶+0∙2⁵+0∙2⁴+0∙2³+0∙2²+0∙2¹+1∙2⁰=64+0+0+0+0+0+1=65₁₀

 

Віднімання

 

0-0=0

1-0=1

1-1=0

10₂-1=1

Знайдемо: 111010111₂-1100001₂

 

     111010111₂

    - 1100001₂

    101110110₂

 

4

Крапки, поставлені над деякими розрядами, показують, що в двійковій системі одиниця відміченого розряду роздроблюється на дві одиниці вищого розряду.

Множення

 

11101₂∙1101₂

11101_{2 -} множник

1101₂ - множник

11101 - множене

+11101 - множене, зсунуте на 2 розряди вліво

11101 - множене, зсунуте на 3 розряди вліво

101111001₂ - добуток

Перевірка:

 

11101₂=1∙2⁴+1∙2³+1∙2²+0∙2¹+1∙2⁰=16+8+4+1=29₁₀

1101₂=13₁₀; 29∙13=377₁₀

101111001₂=1∙2⁸+0∙2⁷+1∙2⁶+1∙2⁵+1∙2⁴+1∙2³+0∙2²+0∙2¹+1∙2⁰=256+0+64+32+16+8++0+1=377_10.

Отже, в двійковій арифметиці при множенні не потрібна таблиця множення. Не треба знаходити добутки першого множника на значення послідовних розрядів другого множника, так як значення цих розрядів або 1 або 0.

Достатньо записати значення першого множника одне під одним із зсувом на один розряд; у випадку рівності якого-небудь розряду другого множника нулю, його зсувають на два розряди.

  1101111₂

    101101₂

    1101111

1101111

1101111

   1101111 __

1001110000011₂

 

Системи числення з довільною основою

 

Ми розглянули алгоритм переводу чисел з двiйково системи числення в десяткову i навпаки - з десятково в двiйкову. Алгоритми залишаться цiлком аналогiчними, якщо замiсть двiйково системи числення взяти будь-яку iншу.

Нехай, наприклад, деяке число записане в вiciмковiй системi числення. Це значить, що цифри в записі цього числа  кофiцiєнти в його розкладi по степенях числа 8:

 

(a_na_n-1... a₁a₀, a_-1a_-2..) ₈ =a_n*8ⁿ+a_n-1*8^n-1+... +a₁*8+a₀+a_-1*8^-1+...

 

Для того,щоб отримати зображення цього числа в десятковiй системi числення, достатньо виконати, користуючись десятковою арифметикою, всi операцi в правiй частинi цього виразу. Приклад. Перевести число (276,54) ₈ з вiсiмково системи числення в десяткову:

 

(276,54) ₈=2*8²+7*8¹+6*8⁰+5*8^-1+4*8^-2=128+56+6+5/8+4/64= (190,6875) ₁₀.

 

Нехай тепер потрiбно перевести число з десятково системи числення в вiсiмкову. Як i у випадку переводу в двiйкову систему числення, розглянемо окремо цiлу i дробову частини чисел. Для цiло частини скористамось алгоритмом дiлення, а для дробово - множення. В першому випадку ми отримам шукане вiсiмкове зображення цiлого числа, зiбравши в зворотньому порядку залишки вiд дiлення на 8, а у другому випадку отримаємо вiсiмкове зображення дробу, зiбравши в прямому порядку цiлi частини при послiдовному множеннi на 8. Приклад. Перевести число (190,6875) ₁₀ з десятково системи числення в вiсiмкову.

Переведемо цiлу частину:

 

       190 | 8

       16 | 23 | 8

        30    16 | 2 | 8             (190)₁₀=(276)₈

8

       6 7 2 | 0

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

 

             0 | 6875                      (0,6875)₁₀=(0,54)₈                

                 5 | 5000

                 4 | 0                     

тобто (190,6875)₁₀ =(276,54)₈.

 

Цей приклад разом з попереднiм iлюстру, як можна перевiряти правильнiсть переводу з однiє системи числення в iншу зворотнiм переводом.

Виконання арифметичних дій в СЧ з основою р.

Змішані СЧ. Запис чисел в змішаних СЧ. Системи з кратними основами. Теорема для СЧ з кратними основами

 

Мшан системи числення

 

Існує простий спосб запису десяткових чисел за допомогою двйкових цифр - представлення чисел в мшанй двйково-десятковй систем числення. В нй кожна цифра десяткового зображення числа записуться в двйковй систем числення.

Причому для того, щоб такий запис був однозначним, для представлення будь-якої десятково цифри вдводиться одна  та ж кльксть двйкових розрядв - чотири. Якщо десяткова цифра вимага для свого представлення менше значущих двйкових цифр, то попереду цих цифр дописуються нул (так щоб загальна кльксть двйкових знакв залишалась рвною чотирьом). Наприклад, десяткове число 834,25 в двйково-десятковй систем запишеться так:

 

(834,25) ₁₀ = (1000 0011 0100,0010 0101).

Кожна четврка (тетрада) двійкових цифр тут вдповда однй десятковй цифр:

 

                    (8)₁₀ = (1000)_2-10                  (2)₁₀ = (0010)_2-10

                    (3)₁₀ = (0011)_2-10                  (5)₁₀ = (0101)_2-10

                    (4)₁₀ = (0100)_2-10

 

11

Теорема. Якщо P = Qⁿ (P, Q, n - цл додатн числа), то запис любого числа в мшанй (Q - P) - й систем числення тотожньо спвпада з записом цього ж числа в систем числення з основою Q (з точнстю до нулв на початку запису цло частини числа  на кнц дробово).

Якщо P=8, Q=2, n=3, то 8=2³ , отже, згдно даної теореми запис будь-якого числа в двйково-всмковй систем спвпада з записом того ж числа в двйковй систем. (Зауважимо, що за тю ж теоремою записи будь-якого числа в двйковй  двйково-шстнадцятковй системах теж спвпадуть). Переведемо, наприклад, все теж число (405) ₁₀ з десятково системи числення в шстнадцяткову:

 

                              405| 16

                                             32 | 25 | 16

                                85 9| 1 | 16

                                80      |0

                                  5

 

Збираючи залишки вд длення, отримамо (405) ₁₀ = (195) ₁₆.

Представимо тепер число (195) ₁₆ в двйково - шстнадцятковому запис: (195) ₁₆ = (1 1001 0101) _2-6.

Видно, що записи числа в двйковй  двйково-шстнадцятковй системах вuявuлuсь однаковими. Ця властивсть двйково-всмково системи числення дозволя дуже просто переводити числа з двйково системи в всмкову (чи шстнадцяткову)  навпаки.

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

Взьмемо, наприклад, код:

 

(10011110, 0011)₂ = (236,14)₈ .

                                   2 3 6 1 4

 

12

Тут, як  в двйково-десятковому записі, в цлй частин вдкинут крайн злва нул, а в дробовй частин - крайн справа. Безумовно, треба х враховувати як недостатн у вдповдних традах двйкових цифр. Зворотнй перевд чисел з всмково системи числення в двйкову також простий. Кожну цифру всмкового числа записумо трйкою двйкових символв, тобто записумо його в двйково-всмковй систем, а так як цей запис спвпада з двйковим, то ми одержимо число в двйковй систем. Переведемо, наприклад, число (3514,72) ₈ з всмково системи в двйкову:

 

(3514,72)₈ = (11101001100, 11101)₂.

                                                   3 5 1 4 7 2    

 

Звдси слду, що всмкову систему числення можна використовувати для скороченого запису любого двйкового коду. При цьому використовується приблизно в двч менше символв, якщо розбити х на трйки цифр  кожну записати одню всмковою цифрою. Так само запис будь-якого числа в шстнадцятковй систем числення можна використовувати для скороченого запису двйкового коду. В цьому випадку кожному шстнадцятковому символу взамно однозначно вдповда набр з чотирьох двйкових цифр:

 

(0)₁₆ = (0000)₂                    (8)₁₆ = (1000)₂

(1)₁₆ = (0001)₂                    (9)₁₆ = (1001)₂

(2)₁₆ = (0010)₂                     (а)₁₆ = (1010)₂ = (10)₁₀

(3)₁₆ = (0011)₂                     (b)₁₆ = (1011)₂ = (11)₁₀

(4)₁₆ = (0100)₂                     (c)₁₆ = (1100)₂ = (12)₁₀ 

(5)₁₆ = (0101)₂                     (d)₁₆ = (1101)₂ = (13)₁₀ 

(6)₁₆ = (0110)₂                     (e)₁₆ = (1110)₂ = (14)₁₀

(7)₁₆ = (0111)₂                     (f)₁₆ = (1111)₂ = (15)₁₀.

 

Так як записи числа в двйково-шстнадцятковй  двйковй системах за сформульованою вище теоремою спвпадають, то, замнивши вс шстнадцятков цифри деякого числа на вдповдн четврки двйкових цифр, отримамо таке ж число в двйковй систем числення. При цьому запис числа буде використовувати приблизно в чотири раза менше цифр, нж в двйковй систем числення. Наприклад, число (3c2e9) ₁₆ може бути представлене в двйковй систем числення наступним чином: (11 1100 0010 1110 1001) ₂.

 

3 c 2 e 9

 

13

Пд кожною четвркою двйкових цифр ми записали вдповдний шстнадцятковий символ. Дві форми комп’ютерного представлення числових даних. Їх переваги і недоліки.