Позиційні системи числення

1.1. Запис натуральних чисел

Система числення – це система запису, або позначення, чисел. Найдосконалішими системами числення виявилися позиційні. У цих системах число, позначене цифрою, залежить від її місця (позиції) в записі числа. Наприклад, звичні нам записи 13 і 31 у десятковій системі складаються з однакових цифр (значків "1" і "3"), але позначають різні числа 1 10+3 і 3 10+1.

Позиційна система числення з основою P (P-кова) має P цифр C0, C1, … , CP-1, що звичайно позначають натуральні числа від 0 до P-1. Ці записи та позначені ними числа – значення цих записів – називаються однорозрядними P-ковими.

Цифри десяткової системи 0, 1, 2, … , 9 називаються арабськими, хоча й були запозичені арабами в індусів.

У програмуванні широко застосовується шістнадцяткова система, в якій перші 10 цифр арабські, а наступні шість – A, B, C, D, E, F. Вони позначають числа, десятковий запис яких 10, 11, 12, 13, 14, 15 відповідно.

Число P у P-ковій системі позначається дворозрядним записом C1C0, число P+1 – записом C1C1 тощо до P P-1. Наприклад, 10, 11, ... , 99 у десятковій системі, 10, 11 у двійковій, 10, 11, … , 1F, 20, … , FF у 16-ковій. Число P P позначається вже трьома цифрами C1C0C0, далі йде C1C0C1 тощо. Наприклад, 100, 101, … , 999 у десятковій системі, 100, 101, 110, 111 у двійковій, 100, 101, … , FFF у 16-ковій. І взагалі, запис вигляду

(akak-1 a1a0)P

позначає в P-ковій системі число, що є значенням полінома

ak Pk+ak-1 Pk-1+ +a1 P+a0.

Наприклад, двійковий запис (10011)2 позначає число, яке в десятковому записі має вигляд 1 24+0 23+0 22+1 21+1 20=19. 16-ковий запис (1BC)16 позначає десяткове 1 162+11 16+12=444.

Найправіша цифра в запису числа позначає кількість одиниць і називається молодшою, найлівіша – кількість чисел Pk і називається старшою.

Ми звикли до десяткового подання чисел, і саме воно, головним чином, використовується в Паскаль-программах, але в комп'ютері числа, як правило, подаються в двійковій системі. Таким чином, виникає необхідність створювати двійкове подання числа за його десятковим записом і навпаки. Зауважимо до речі, що такі перетворення записів чисел з однієї системи в іншу здійснюються при виконанні процедур читання і запису readln і writeln.

За P-ковим записом (akak-1  a1a0)P натурального числа N можна побудувати десяткове подання, обчисливши значення полінома за допомогою операцій множення та додавання в десятковій системі. Саме цим ми займалися двома абзацами вище.

Розглянемо, як одержати за натуральним числом N цифри його P-кового подання. Нехай N=(akak-1  a1a0)P, і кількість цифр k+1 невідомі. Запишемо подання в такому вигляді:

N = ak Pk+ak-1 Pk-1+ +a1 P+a0 = (…(ak P+ak-1) P+ +a1) P+a0.

Звідси очевидно, що значенням a0 є N mod P, a1 – (N div P) mod P тощо. Таким чином, якщо поділити N на P у стовпчик, то остача від ділення буде значенням молодшої цифри. Потім можна так само поділити на P частку від першого ділення – остача буде виражати кількість "P-кових десятків" тощо поки остання частка не виявиться менше P. Вона й буде значенням старшої цифри. При P>10 ще треба перетворити числа більше 9 у цифри. Наприклад, одержимо цифри 16-кового подання десяткового числа 1022:

_1022 | 16 _63 | 16

96 63 48 3

_62 15

48

14

Виділені 14, 15 і 3 – це кількості 16-кових "одиниць", "десятків" і "сотень" відповідно. Позначимо їх 16-ковими цифрами E, F і 3 відповідно та одержимо запис 3FE.

Якщо натуральне N подано в базовому типі цілих, то одержати його P-кові цифри можна за наступним алгоритмом (остання цифра утворюється як остача від ділення на P частки, меншої від P):

while N > 0 do

begin

d:= N mod P ;

за значенням d побудувати P-кову цифру;

N := N div P

end

Якщо позначити цифрами A, B, … , Z числа від 10 до 35, то з використанням відповіді до задачі 10.5 за цим алгоритмом можна утворити подання чисел аж до 36-кової системи.

Для використання ще більших основ систем числення треба додатково розширити алфавіт цифр.

1.2. Дробові числа

P-кове подання чисел, менших 1, має вигляд 0.a-1 a-2  , де a-i – P-кові цифри. Цей запис позначає дійсне число – значення виразу

a-1 P-1+a-2 P-2+ 

Наприклад, (0.1101)2 позначає десяткове

1 2-1+1 2-2+0 2-3+1 2-4=0.5+0.25+0.0625=0.8125;

(0.21)3 – 2 3-1+1 3-2=0.777…=0.(7); (0.BC)16 – 11 16-1+12 16-2=0.734375.

За P-ковим поданням, у якому задано r старших цифр, десятковий запис числа утворюється обчисленням значення многочлена

a-1 P-1+a-2 P-2+ … +a-r P-r.Нагадаємо, що якщо основа P має прості дільники, відмінні від 2 і 5, то число зі скінченним P-ковим записом зображується нескінченним, але періодичним десятковим дробом. Якщо ж простими дільниками P є тільки 2 і 5, то й десятковий дріб скінченний.

Розглянемо, як за дійсним значенням V одержати цифри його P-кового подання. Нехай V=(0.a-1a-2…)P. Запишемо подання в такому вигляді:

V=P-1 (a-1+P-1 (a-2+ )).

Тоді V P=a-1+P-1 (a-2+ ), звідки очевидно, що a-1= V P , і P-1 (a-2+ ) = {V P}, де  V P та {V P} позначають цілу та дробову частини V P. Помноживши {V P} на P і узявши цілу частину, одержимо a-2 тощо. Наприклад, при V=0.75, P=3 одержимо

a-1= 0.75 3 =2, {0.75 3}=0.25, a-2= 0.25 3 =0, {0.25 3}=0.75 тощо.

Таким чином, трійковим поданням 0.75 буде нескінченний періодичний дріб (0.(20))3.

Маючи дійсне значення V, V<1, можна одержати r перших цифр його P-кового подання, виконавши алгоритм

for i := 1 to r do

begin

V := V*P;

d:= trunc ( V ) ;

за значенням d побудувати P-кову цифру;

V := V - trunc ( V )

end.

1.3. "1+1=10, 5 8=28"

Якщо додати 1 і 1, то одержимо 2. Але в двійковій системі це 10, тобто в двійковій системі 1+1=10. При додаванні в стовпчик це означає суму 0 і перенос 1 у наступний розряд. Наприклад, додамо в стовпчик 3 і 6 у двійковій системі:

+ 11

110

1001

У десятковій системі 10+13=23. Те ж саме в шістнадцятковій виглядає як A+D=17. Взагалі, додаючи дві або більше P-кові цифри, у результаті одержуємо

(їх сума) mod P

із переносом (їх сума) div P. Наприклад, у шістнадцятковій системі

+ 9D

FAE

104B

(неважко перевірити, що при додаванні в стовпчик D+E=1B, 1+9+A=14, 1+F=10).

Усі вчаться в школі не тільки додавати, але й множити. Коли ми множимо число в десятковій системі у стовпчик на число, записане одною цифрою X, то обчислюємо добуток чергової цифри числа та X. Остачу від ділення цього добутку на 10 додаємо до переносу від попереднього розряду й одержуємо суму S. Молодшу цифру S, тобто остачу від ділення на 10, записуємо в результат, а старшу, тобто S div 10, запам'ятовуємо як перенос. І так рухаємося від молодшої цифри співмножника до старшої. Знайомо, чи не так?

У P-ковій системі відбувається те ж саме, тільки остачі беруться від ділення не на 10, а на P. Наприклад, у шістнадцятковій системі 5 8 при діленні на 16 дає остачу 8 і частку 2, тобто 5 8=28. У вісімковій системі

 1234

7

11102

(4 7 при діленні на 8 дає 2 в остачі й 3 у переносі, 3 7+3 дає 0 і 3 тощо).

Множення на число, у якого більше однієї цифри, зводиться до множень на окремі цифри, запису результатів із зсувом та додавання у стовпчик. Наприклад, у вісімковій системі

 77

123

275

176

77 .

12155

Аналогічно в шістнадцятковій системі

 FE

20A

9EC

1FC .

205EC