Системы счисления, или Как считает компьютер?

Системы счисления
Система счисления (numbering system) - совокупность приемов и правил для записи чисел знаками.
Способов записи чисел цифровыми знаками существует бесчисленное множество.
Наиболее известна десятичная система счисления, в которой для записи чисел используются цифры 0, 1, … , 9.
Любая предназначенная для практического применения система счисления должна обеспечивать:
возможность представления любого числа в рассматриваемом диапазоне величин;
единственность представления (каждой комбинации символов должна соответствовать одна и только одна величина);
простоту оперирования числами

Непозиционные системы счисления
Непозиционная система счисления – система, для которой численное значение символа (цифры) не зависит от его положения в числе.
Например, система с одним символом-палочкой встречалась у многих народов. Для изображения какого-то числа в этой системе нужно записать количество палочек, равное данному числу.
2=II 5=IIIII 10=IIIIIIIIII 1250=IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII…..
Эта система неэффективна, так как запись числа получается длинной.
Основной недостаток всех непозиционных систем – громоздкость записи и трудность выполнения арифметических действий
IIIIIIIIIIIII x IIIIIIIIIIIIII=?

Римская система использует набор следующих символов (цифр):
I - "один";
V - "пять";
X - "десять";
L - "пятьдесят";
C - "сто";
D - "пятьсот";
M - "тысяча"
Самая известная «почти» непозиционная
система счисления - римская
В этой системе существует отклонение от правила независимости значения цифры от положения в числе. В числах LX и XL символ X принимает два различных значения: +10 – в первом случае и –10 – во втором случае.
Запись больших чисел громоздка: 1994=MDCCCCLXXXXIV
Выполнение арифметических операций крайне затруднено:
XXXVII
IX
______
??????

Позиционные системы счисления
Позиционная система счисления – система, в которой значение символа (цифры) определяется его положением в числе: один и тот же знак принимает различное значение. Например, в десятичном числе 222 первая цифра справа означает две единицы, соседняя с ней – два десятка, а левая – две сотни.
Любая позиционная система характеризуется основанием. Основание (базис) позиционной системы счисления – количество знаков или символов, используемых для изображения числа в данной системе.
Позиционные системы счисления имеют ряд преимуществ перед непозиционными: удобство выполнения арифметических и логических операций, а также представление больших чисел, поэтому и людьми, и в цифровой технике применяются позиционные системы счисления.

Различные используемые позиционные системы счисления
В общем виде для любой позиционной системы счисления с основанием B число из n цифр имеет вид:
AB=a1Bn-1+a2B n-2 +...+anB0
Например:
12310=1*103-1+2*103-2+3*103-3
Каждая система счисления имеет свои правила арифметики (таблицы умножения, сложения). Поэтому, производя какие-либо операции над числами, надо помнить о системе счисления, в которой они представлены.

Если основание больше 10…
Если основание системы q превышает 10, то цифры, начиная с 10, при записи обозначают прописными буквами латинского алфавита: A,B,...,Z. При этом цифре 10 соответствует знак 'A', цифре 11 - знак 'B' и т.д.
В таблице приведены десятичные числа от 0 до 15 и их эквивалент в различных системах счисления.

Применение различных систем счисления
Десятичная (число пальцев на руках) – исторически стала единственной системой, применяемой населением Земли.
В двоичной системе работает электронная техника, так как всего две цифры 0 и 1 легче всего представить в виде электрических сигналов
В шестнадцатеричной системе представляются многие числа в Интернете (скажем, так кодируется цвет в HTML):
background=#ffffff;

Общий метод перевода чисел
из одной СС в другую
Перевод целых чисел из системы с основанием q1 в систему с основанием q2 осуществляется делением на основание q2 новой системы счисления, правильных дробей – умножением на основание q2. Действия деления и умножения выполняются по правилам q1-арифметики. Перевод дробей осуществляется раздельно по указанным правилам, результат записывается в виде новой дроби в системе с основанием q2.

Пример. Перевести десятичное число A = 6110 (q1 = 10) в двоичную систему счисления (q2 = 2).
61 | 2
60 30 | 2
b0 = 1 30 15 | 2
b1 = 0 14 7 | 2
b2 = 1 6 3 | 2
b3 = 1 2 1 = b5
b4 = 1
Полученные остатки от деления записываем по порядку появления в ряд справа налево
Получаем правильный ответ: 6110 = 1111012

Табличный метод перевода
В простейшем виде табличный метод заключается в следующем: имеется таблица всех чисел одной системы с соответствующими эквивалентами из другой системы; задача перевода сводится к нахождению соответствующей строки таблицы и выбору из нее эквивалента. Такая таблица очень громоздка и требует большой емкости памяти для хранения.
Другой вид табличного метода заключается в том, что имеются таблицы эквивалентов в каждой системе только для цифр этих систем и степеней основания (положительных и отрицательных); задача перевода сводится к тому, что в выражение ряда для исходной системы счисления надо поставить эквиваленты из новой системы для всех цифр и степеней основания и произвести соответствующие действия (умножения и сложения) по правилам q2-арифметики. полученный результат этих действий будет изображать число в новой системе счисления.

Пример табличного метода перевода
Пример. Перевести десятичное число A = 11310 в двоичную систему счисления, используя таблицу эквивалентов цифр и степеней основания.
Ответ: 11100012.
Решение. Подставив значения двоичных эквивалентов десятичных цифр и степеней основания, получим:

Какие бывают числа
Все эти числа надо каким-то образом представлять в памяти компьютера, выражая их в двоичной системе счисления

Представление действительных
чисел в компьютере
Для представления действительных (вещественных) чисел в современных компьютерах принят способ представления с плавающей запятой (floating point). Этот способ представления опирается на нормализованную (экспоненциальную) запись действительных чисел.
Как и для целых чисел, при представлении действительных чисел в компьютере используется двоичная система, следовательно, предварительно десятичное число должно быть переведено двоичную систему.
Нормализованная запись отличного от нуля действительного числа - это запись вида a=±m·Pq, где q - целое число (положительное, отрицательное или ноль), а m - правильная дробь. При этом m называется мантиссой числа, q - порядком числа.

Представление вещественных чисел
в компьютере
Примеры:
3,1415926 = 0, 31415926 * 101;
1000=0,1 * 104;
0,123456789 = 0,123456789 * 100;
0,00001078 = 0,1078 * 8-4; (порядок записан в десят. системе)
1000,00012 = 0, 100000012 * 24.
Нормализованная запись нуля в десятичной системе будет такой: 0 = 0,0 * 100.

Представление чисел
с плавающей точкой
При представлении чисел с плавающей точкой часть разрядов ячейки памяти отводится для записи порядка числа, остальные разряды - для записи мантиссы. По одному разряду (биту) в каждой группе отводится для изображения знака порядка и знака мантиссы. Для того чтобы не хранить знак порядка, был придуман так называемый смещенный порядок, который рассчитывается по формуле
2a-1 -1+ ИП (истинный порядок)
где a - количество разрядов, отводимых под порядок.
Пример:
Если истинный порядок равен -5, тогда смещённый порядок для 4-байтового числа (из которых 1 байт выделен на порядок) будет равен 28-1-1+(-5)=128-1+(-5)=122.

Алгоритм представления числа
с плавающей запятой
перевести число из P-ичной системы счисления в двоичную;
представить двоичное число в нормализованной экспоненциальной форме;
рассчитать смещённый порядок числа;
разместить знак, порядок и мантиссу в соответствующие биты ячейки памяти.
Пример:
Представить число -25,625 в машинном виде с использованием 4 байтового представления (где 1 бит отводится под знак числа, 8 бит - под смещённый порядок, остальные биты - под мантиссу).

Этап 1: Представление числа -25,625 в двоичном виде
0,62510 = 0,1012;
-25,62510 = -11001,1012.
2510 = 110012;
Целая часть:
Дробная часть:

Этап 2: Преобразование в экспоненциальную форму:
Представление действительного числа не очень удобно изображать в двоичной системе, поэтому часто используют шестнадцатеричное представление:
Этап 3: Расчет смещенного порядка:
Этап 4: Заносим все это в ячейку памяти:

Двоичная арифметика - сложение
Пример. Сложить двоичные числа 11012 и 110112.
Запишем слагаемые в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:
5 4 3 2 1
+ 1 1 0 1
1 1 0 1 1
разряд 1: 1 + 1 = 10; 0 остается в разряде 1, 1 переносится во второй разряд;
разряд 2: 0 + 1 + 1 = 10, где вторая 1 - единица переноса; 0 остается в разряде 2, 1 переносится в третий разряд;
разряд 3: 1 + 0 + 1 = 10, где вторая 1 - единица переноса; 0 остается в разряде 3, 1 переносится в разряд 4;
разряд 4: 1 + 1 + 1 = 11, где третья 1 - единица переноса; 1 остается в разряде 4, 1 переносится в пятый разряд;
разряд 5: 1 + 1 = 10; где вторая 1 - единица переноса; 0 остается в разряде 5, 1 переносится в шестой разряд.

Таким образом:
1 1 0 1
+ 1 1 0 1 1
1 0 1 0 0 0
Поскольку 13 + 27 = 40, двоичное сложение выполнено верно.
Для проверки определим десятичные значения слагаемых и результата:

Двоичная арифметика - вычитание
Пример. Вычесть из двоичного числа 1012 двоичное число 112.
Запишем алгебраические слагаемые в столбик в порядке "уменьшаемое - вычитаемое" и пронумеруем разряды, присвоив младшему разряду номер 1:
3 2 1
-1 0 1
1 1
разряд 1: 1 - 1 = 0;
разряд 2: поскольку 0 меньше 1 и непосредственное вычитание невозможно, занимаем для уменьшаемого единицу в старшем разряде. Тогда разряд 2 рассчитывается как 10 - 1 = 1;
разряд 3: поскольку единица была занята в предыдущем шаге, в разряде остался 0.

Таким образом:
1 0 1
- 1 1
1 0
Для проверки определим десятичные значения слагаемых и результата:
1012 = 5;
112 = 3;
102 = 2.
Поскольку 5 - 3 = 2, вычитание выполнено верно.

Двоичная арифметика - умножение
Пример. Умножить двоичное число 1012 на двоичное число 112.
Запишем множители в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:
3 2 1
1 0 1
1 1
умножение множимого на разряд 1 множителя дает результат: 1012 * 12 = 1012;
умножение множимого на разряд 2 множителя дает результат: 1012 * 102 = 10102. Здесь значение разряда 2 множителя сформировано по принципам формирования значения числа в позиционных системах счисления;
для получения окончательного результата складываем результаты предыдущих шагов: 1012 + 10102 = 11112.

Двоичная арифметика - деление
Пример. Разделить двоичное число 11112 на двоичное число 112.
Решение задачи представим схемой:
Для проверки правильности результата преобразуем двоичные числа в десятичные:
11112 = 15;
112 = 3;
15 / 3 = 5;
5 = 1012.
Деление выполнено верно.

Как считает компьютер
Структура компьютера с хранимой программой
по Дж. фон Нейману