Системы счисления

1. Основные определения
2. Вид числа в позиционной системе счисления
3. Двоичная система счисления
4. Восьмеричная и шестнадцатеричная системы счисления
5. Изображение чисел одной системы счисления с помощью цифр другой системы счисления
6. Перевод чисел из некоторой позиционной системы счисления в десятичную систему счисления
7. Перевод чисел из десятичной системы счисления в некоторую позиционную систему счисления
8. Перевод чисел в случае кратных оснований систем счисления

1. Основные определения

Система счисления - совокупность приемов записи чисел. Алфавит системы счисления - упорядоченное множество символов для записи чисел. Цифра - элемент алфавита системы счисления. Основание системы счисления - количество цифр в алфавите. Система счисления определяет способ записи чисел, при котором используются цифры алфавита.

Позиционные системы счисления - системы, в которых значение каждой цифры зависит от ее места в изображении числа. Позиционные системы счисления также называются аддитивно-мультипликативными. Непозиционные системы счисления - системы, в которых значение каждой цифры не зависит от ее места в изображении числа. Непозиционные системы счисления также называются аддитивными.

1. Десятичная система счисления:
   позиционная (аддитивно-мультипликативная), алфавит {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
2. Римская система счисления:
   непозиционная (аддитивная), алфавит {I, V, X, L, C, D, M}, где I =1, V=5, X=10, L=50, C=100, D=500, M=1000.
   Правила построения чисел:
   • Если цифра справа меньше либо равна цифре слева, то эти цифры складываются (например, VII=7, XVI=16).
   • Если цифра слева меньше, чем цифра справа, то левая цифра вычитается из правой (например, IV=4, XL=40).

2. Вид числа в позиционной системе счисления

Пусть имеется позиционная система счисления с основанием P и алфавитом A_P={0,1,2, ..., P} и вещественное число X, записанное цифрами этого алфавита в виде a_na_n-1a_n-2...a₁a₀,a_-1a_-2...a_-m (цифры в записи числа - разряды; разряды нумеруются с 0; n - количество разрядов в десятичной части числа, m - количество разрядов в дробной части числа). Тогда X представимо в виде полинома X=a_nPⁿ+a_n-1P^n-1+...+a₁P¹+a₀P⁰+a_-1P^-1+a_-2P^-2+...+a_-mP^-m.

Основание системы счисления показывает соотношение весов цифр соседних разрядов.

Пример:

1237,089=1*10³+2*10²+3*10¹+7*10⁰+0*10^-1+8*10^-2+9*10^-3

3. Двоичная система счисления

В компьютерах используется в основном двоичная система счисления. Одна из основных причин - для ее реализации нужны технические устройства только с двумя устойчивыми состояниями ("есть ток"-"нет тока" и т.д., а не, например, с десятью, - как в десятичной системе счисления). Алфавит A₂={0,1}.

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

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

Примеры:

10111₂+1101₂=100100₂; 10111₂*1101₂=100101011₂; 10111₂-1101₂=1010₂. (Проверьте вручную, используя таблицы сложения и умножения!)

4. Восьмеричная и шестнадцатеричная системы счисления

Двоичная система счисления приводит к громоздкой записи чисел, поэтому для кодирования используют также 8-ю и 16-ю системы счисления. Алфавит A₈={0,1,2,3,4,5,6,7}. Алфавит A₁₆={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}(используются латинские буквы, т.к. для записи алфавита не хватает арабских цифр).

5. Изображение чисел одной системы счисления с помощью цифр другой системы счисления

Для изображение чисел системы счисления с основанием P с помощью цифр системы счисления с основанием Q (Q<P) используется смешанная система счисления (Q-P)-ичная со старшим основанием P и младшим основанием Q. Для представления числа в смешанной системе счисления каждая его цифра из A_P заменяется на соответствующую цифру из A_Q, причем используется всегда такое количество Q-ичных разрядов, которое достаточно для представления любой цифры из A_P.

Примеры:

Для изображения любой 10-чной цифры требуется 4 двоичных разряда. Тогда 723₁₀=0111 0010 0011_2-10. Для изображения любой 8-чной цифры требуется 3 двоичных разряда. Тогда 723₈=111 010 011_2-8.

6. Перевод чисел из некоторой позиционной системы счисления в десятичную систему счисления

Пусть имеется число X, записанное P-ичной системе счисления в виде a_na_n-1a_n-2...a₁a₀,a_-1a_-2...a_-m и требуется найти представление X в 10-й системе счисления.

Для перевода необходимо вычислить полином X=a_nPⁿ+a_n-1P^n-1+...+a₁P¹+a₀P⁰+a_-1P^-1+a_-2P^-2+...+a_-mP^-m, где цифры a_i заменяются их десятичными изображениями и операции выполняются в  10-й системе счисления.

Пусть требуется перевести 547₈ в 10-чную систему счисления. Запишем число в виде в виде полинома и выполним действия в 10-чной системе счисления. Получим 5*8²+4*8¹+7*8⁰=359. Таким образом, 547₈ есть 359₁₀.

Пусть требуется перевести DF,3₁₆ в 10-чную систему счисления.  Запишем число в виде в виде полинома и выполним действия в 10-чной системе счисления. Получим 13*16²+15*16¹+3*16^-1=223,1875. Таким образом, DF,3₁₆ есть 223,1875₁₀.

7. Перевод чисел из десятичной системы счисления в некоторую позиционную систему счисления

Пусть целое число X задано в 10-чной системе счисления и требуется перевести его в систему счисления с основанием Q, т.е. найти цифры b_i для записи X=b_s*Q^s+b_s-1*Q^s-1+ ... +b₀*Q⁰.

Для определения b₀ разделим левую и правую части равенства на Q, причем в левой части деление выполняется по правилам 10-чной арифметики. Имеем: X/Q=b_sQ^s-1+b_s-1Q^s-2+...+b₁+b₀ /Q. Представим левую часть равенства  как сумму целой и дробной частей X/Q=[X/Q]+{X/Q}и приравняем их с целой и дробной частями правой части равенства: [X/Q]=b_sQ^s-1+b_s-1Q^s-2+...+ b₁ и {X/Q}=b₀/Q. Таким образом, цифра b₀ является остатком от деления X на Q (деление выполняется в 10-чной системе счисления).

Далее положим X₁=X/Q=b_sQ^s-1+b_s-1Q^s-2+...+ b₁ и повторим аналогичные действия для определения цифры b₁. Цифра b₁ является остатком от деления X₁ на Q (деление выполняется в 10-чной системе счисления).

Таким образом, перевод числа X осуществляется по следующим рекуррентным формулам:

• bi=Q{X_i/Q}, т.е.  цифра bi есть остаток от деления X_i на Q;

• X_i+1=[X_i/Q], т.е. целая часть от деления X_i на Q (i=0, 1, 2, …; X₀=X); процесс продолжается до тех пор, пока не будет получено X_i+1=0.

Словесная формулировка: Для перевода целого 10-чного числа X в систему счисления с основанием Q необходимо X разделить нацело на Q, записанное в 10-чной системе счисления. Затем полученное неполное частное нужно снова разделить нацело на  Q. Процесс продолжать до тех пор, пока последнее полученное неполное частное не станет равным нулю. Представлением числа X будет последовательность остатков деления, изображенных одной Q-чной цифрой и записанных в порядке, обратном порядку их получения.

Перевести число 55₁₀ в 2-чную систему счисления. 55=27*2+1; 27=13*2+1; 13=6*2+1; 6=3*2+0; 3=1*2+1; 1=0*2+1. Таким образом, 55₁₀=110111₂.

Перевести число 2058₁₀ в 16-чную систему счисления. 2058=128*16+10; 128=8*16+0; 8=0*16+8. Таким образом, 2058₁₀=80A₁₆.

Пусть X - правильная дробь, заданная в 10-чной системе счисления и требуется перевести ее в систему счисления с основанием Q, т.е. найти цифры b_i для записи X=b_-1*Q^-1+b_-2*Q^-2+ ... +b_-m*Q^-m.

Для определения bi умножим левую и правую части равенства на Q, причем в левой части умножение выполняется по правилам 10-чной арифметики. Имеем: X*Q=b_-1+b_-2Q^-1+...+b_-mQ^-m+1. Представим левую часть равенства  как сумму целой и дробной частей X*Q=[X*Q]+{X*Q}и приравняем их с целой и дробной частями правой части равенства: [X*Q]=b_-1 и {X*Q}=b_-2Q^-1+...+b_-mQ^-m+1. Таким образом, цифра b_-1 является целой частью от умножения X на Q (умножение выполняется в 10-чной системе счисления). Далее положим X₁=X*Q и повторим аналогичные действия для определения цифры b_-2.

Таким образом, перевод правильной дроби X осуществляется по следующим рекуррентным формулам:

• b_-i-1=[X_i*Q].

• X_i+1={X_i*Q}, i=0, 1, 2, …; процесс продолжается до тех пор, пока не будет получено X_i+1=0 или не будет получена требуемая точность изображения числа (требуемое количество цифр после запятой).

Словесная формулировка: Для перевода правильной десятичной дроби X  в систему счисления с основанием Q необходимо X умножить на Q, записанное в 10-чной системе счисления. Затем дробную часть полученного произведения снова умножить на Q. Процесс продолжать до тех пор, пока последнее полученное произведение не станет равным нулю, либо не будет достигнута требуемая точность изображения числа X. Представлением числа X будет последовательность целых частей полученных произведений, изображенных одной Q-чной цифрой и записанных в порядке их получения.

Примеры:

Перевести число 0,36₁₀ в 2-чную систему счисления c 5 знаками после запятой. 0,36*2=0+0,72; 0,72*2=1+0,44; 0,44*2=0+0,88; 0,88*2=1+0,76; 0,76*2=1+0,52.  Таким образом, 0,36₁₀=0,01011₂.

Перевести число 0,36₁₀ в 16-чную систему счисления c 2 знаками после запятой. 0,36*16=5+0,76; 0,76*16=12+0,16.  Таким образом, 0,36₁₀=0,5С₁₆.

При переводе числа X из P-чной системы счисления в Q-чную в случае, если P=Q^k (k - целое положительное), запись X_Q-P в смешанной (Q-P)-чной системе счисления тождественно совпадает с записью X_Q в Q-чной системе счисления. Например, 8=2³ и 16=2⁴, поэтому для записи 8-чного числа в 2-чной системе счисления достаточно заменить каждую его цифру на соответствующее 3-разрядное двоичное число (соответствующую двоичную триаду), а для записи 16-чного числа в 2-чной системе счисления достаточно заменить каждую его цифру на соответствующее 4-разрядное двоичное число (соответствующую двоичную тетраду). А для перевода двоичных чисел в 8-чную и 16-чную системы счисления необходимо разбить число соответственно на триады и тетрады (добавляя при необходимости нули слева от целой части и справа от дробной части) и заменить их на соответствующие 8-чные и 16-чные цифры.