Системы счисления: различия между версиями

Содержимое удалено Содержимое добавлено
м Откат правок 92.241.105.35 (обс.) к версии 178.218.40.159
Строка 50:
Примером «чисто» '''непозиционной''' системы счисления является римская система.
 
== Позиционные системы счисления ==
111111111111
=== Введение ===
Позиционные системы счисления — это системы счисления, в которых значение цифры напрямую зависит от её положения в числе.<br />
Например, число 01 обозначает единицу, 10 — десять.
 
Позиционные системы счисления позволяют легко производить арифметические расчёты.
1
 
Представление чисел с помощью арабских цифр — самая распространённая позиционная система счисления, она называется «десятичной системой счисления». Десятичной системой она называется потому, что использует десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Заметьте: максимальная цифра (9) на единичку меньше количества цифр (10).
 
Для составления машинных кодов удобно использовать не десятичную, а двоичную систему счисления, содержащую только две цифры, 0 и 1. Обратите внимание, что в двоичной системе максимальная цифра 1.
 
Программисты для вычислений также пользуются ещё восьмеричной и шестнадцатеричной системами счисления.
 
Количество цифр, используемых в системе счисления, называется её «основанием».
В десятичной системе основание равно десяти, в двоичной системе — двум, ну а в восьмеричной и шестнадцатеричной — соответственно, восьми и шестнадцати.
То есть в р-ичной системе счисления количество цифр равно р и используются цифры от 0 до р-1.
 
В общем случае в позиционной системе счисления числа представляются следующим образом: <math>a_{n-1} ...a_1a_{0f}</math>, где <math>a_0, a_1, ..., a_{n-1}</math> — цифры, а <math>f</math> — основание системы счисления. Если используется десятичная система, то <math>f</math> — можно опустить.
 
Примеры чисел:
* <math>25_{10}</math> — число в десятичной системе счисления, <math>a_0=5, a_1=2</math>;
* <math>31_8</math> — это же число в восьмеричной системе счисления, <math>a_0=1, a_1=3</math>;
* <math>221_3</math> — это же число в несимметричной [[w:Троичная система счисления|троичной системе счисления]], <math>a_0=1, a_1=2, a_2=2</math>;
* <math>11001_2</math> — это же число в двоичной системе счисления, <math>a_0=1, a_1=0, a_2=0, a_3=1, a_4=1</math>;
 
=== Зависимость плотности записи информации от основания системы счисления ===
Удельная натуральнологарифмическая плотность записи числа зависит от основания системы счисления х и выражается функцией y=ln(x)/x. Эта функция имеет максимум при x=e=2,718281828….
 
То есть система счисления с наибольшей плотностью записи имеет '''нецелочисленное''' основание.
 
Из '''целочисленных''' систем счисления наибольшей плотностью записи информации обладает троичная система счисления, то есть система с основанием равным трём.
 
Эту задачу решали ещё во времена Непера, в результате для уменьшения таблиц и числа вычислений перешли к таблицам натуральных логарифмов с основанием равным числу Эйлера е=2,718281828… .
 
=== Преобразование чисел ===
Такое представление чисел обозначает вот такое число: <math>a_{n-1} f^{n-1} + ... + a_1 f^1 + a_0 f^0</math>, где <math>a_0, a_1, ..., a_{n-1}</math> — цифры, а <math>f</math> — основание системы счисления.
 
Посмотрим чему равны числа из примеров. Используем только что приведённую формулу:
* <math>25_{10} \rightarrow 2 \cdot 10^1 + 5 \cdot 10^0 = 2 \cdot 10 + 5 \cdot 1 = 25_{10}</math>;
* <math>31_{8} \rightarrow 3 \cdot 8^1 + 1 \cdot 8^0 = 3 \cdot 8 + 1 \cdot 1 = 25_{10}</math>;
* <math>221_3 \rightarrow 2 \cdot 3^2 + 2 \cdot 3^1 + 1 \cdot 3^0 = 2 \cdot 9 + 2 \cdot 3 + 1 \cdot 1 = 25_{10}</math>;
* <math>11001_2 \rightarrow 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 1 \cdot 16 + 1 \cdot 8 + 0 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 25_{10}</math>.
 
Мы разобрали, как узнать, чему равно число в любой системе счисления. Но как нам получить это число? Представим что у нас есть некоторое число <math>A</math>, и мы хотим получить его представление в системе по основанию <math>f</math>. Как нам это сделать?
 
Мы знаем, что число <math>A</math> можно представить в виде <math>a_{n-1} a_{n-2} ... a_{0f}</math>, будем из этого исходить. Что будет, если мы поделим это число на <math>f</math>. Получим
 
<center><math>{{a_{n-1} f^{n-1}+ ... a_2 f^2+a_1 f^1+a_0 f^0} \over f} = a_{n-1} f^{n-2}+ ... +a_2 f^1+a_1 f^0</math></center>
и остаток от деления <math>a_0</math>. Почему <math>a_0</math>? Все члены суммы делятся на <math>f</math> без остатка, а последний член <math>a_0</math> в результате деления даёт <math>0</math> и <math>a_0</math> в остатке, так как максимальное значение цифры всегда на единичку меньше основания системы. Итак мы получили самую правую цифру <math>a_0</math>, как остаток от деления, и число <math>a_{n-1} a_{n-2} ... a_{1f}</math>, как результат деления числа <math>A</math> на <math>f</math>. Если мы так будем продолжать делить, то получим все цифры <math>a_1, a_2 ... a_{n-1}</math>.
 
Возьмём для примера полюбившееся нам число <math>25</math> и получим представление этого числа в двоичной системе счисления:
 
* <math>25/2 = 12</math>, остаток <math>1</math>;
* <math>12/2 = 6</math>, остаток <math>0</math>;
* <math>6/2 = 3</math>, остаток <math>0</math>;
* <math>3/2 = 1</math>, остаток <math>1</math>;
* <math>1/2 = 0</math>, остаток <math>1</math>.
 
Что и следовало ожидать, получили: <math>11001_2</math>.
 
Представим число 25 в троичной системе счисления:
 
* <math>25/3 = 8</math>, остаток <math>1</math>;
* <math>8/3 = 2</math>, остаток <math>2</math>;
* <math>2/3 = 0</math>, остаток <math>2</math>.
 
Получили число: <math>221_3</math>.
 
Для закрепления наших знаний проделаем вычисления для восьмеричной и десятичной систем счисления.
 
Восьмеричная система счисления:
* <math>25/8 = 3</math>, остаток <math>1</math>;
* <math>3/8 = 0</math>, остаток <math>3</math>.
 
Результат: <math>31_8</math>.
 
Десятичная система счисления:
* <math>25/10 = 2</math>, остаток <math>5</math>;
* <math>2/10 = 0</math>, остаток <math>2</math>.
 
Результат: <math>25_{10}</math>.
 
Чтобы ещё лучше понять перевод в различные системы счислений, посмотрим, какие трансформации происходят внутри числа <math>4567_{10}</math>.
 
Представим это число в виде
 
<center><math>4 \cdot 10^3+5 \cdot 10^2+6 \cdot 10^1+7 \cdot 10^0=4 \cdot 1000+5 \cdot 100+6 \cdot 10+7</math>.</center>
 
Посмотрим, что у нас получится при последовательном делении на <math>10</math>:
* делим на <math>10</math>, получаем <math>4 \cdot 100+5 \cdot 10+6</math> и <math>7</math> в остатке;
* делим ещё раз на <math>10</math>, получаем <math>4 \cdot 10+5</math> и <math>6</math> в остатке;
* и ещё раз делим на <math>10</math>, получаем <math>4</math> и <math>5</math> в остатке;
* делим в последний раз на <math>10</math>, получаем <math>0</math> и <math>4</math> в остатке.
 
=== Шестидесятеричная система счисления ===
То, как мы представляем время на часах, это пример шестидесятеричной позиционной системы счисления. В представлении времени используется три позиции: для часов, минут и секунд; так как для каждой позиции приходится использовать 60 цифр, а у нас только десять цифр, то для каждой шестидесятиричной позиции используется две десятичные цифры (00, 01, 02, …, 59), а позиции разделяются двоеточием.
 
<center>h: m: s</center>
 
Чтобы получить время в секундах мы должны посчитать вот по такой формуле:
 
<center><math>h 60^2 + m 60^1 + s 60^0 = h 3600 + m 60 + s</math></center>.
 
Рассмотрим действия с шестидесятеричной системой на двух небольших задачках:
# Пирог нужно печь в духовке 45 минут, сколько это будет в секундах?
# Нужно испечь десять пирогов, сколько потребуется времени?
 
Чтобы производить вычисления в шестидесятеричной системе счисления нужно знать таблицу сложений и умножений шестидесятеричных чисел. Каждая таблица очень большая, она размером 60х60 ячеек, мы то обычную таблицу умножения еле запомнили, а уж выучить шестидесятиричную таблицу умножения нам врядли окажется по силам.
 
Чтобы решить эти задачи можно посчитать всё в десятичной системе, а потом результат перевести назад в шестидесятиричную систему.
 
Приступим. Чтобы перевести 45 минут в количество секунд, нужно просто, подставить числа в верхнюю формулу: h равняется нулю, m равняется 45 и s — нулю, получаем
 
<center><math>0 \cdot 3600 + 45 \cdot 60 + 0 = 2700</math></center>.
Ответ на первый вопрос: пирог нужно печь в духовке 2700 секунд.
 
Чтобы узнать сколько потребуется времени чтобы испечь десять пирогов нужно время готовки умножить на количество пирогов, то есть на десять. <math>2700 \cdot 10 = 27000</math>, но это время в секундах, а нам бы хотелось получить время в привычных нам часах, минутах и секундах, для этого воспользуемся стандартным способом перевода из одной системы счисления в другую, делением на основание системы счисления. Приступим:
* <math>27000/60 = 450</math> и <math>0</math> в остатке, записываем остаток в младший разряд хх: хх:00;
* <math>450/60 = 7</math> и <math>30</math> в остатке, записываем остаток в следующий разряд хх:30:00;
* <math>7/60 = 0</math> и <math>7</math> в остатке, записываем остаток в старший разряд 07:30:00.
 
Ответ на второй вопрос: чтобы испечь десять пирогов потребуется 7 часов 30 минут и 0 секунд.
 
== Двоичная система счисления ==
В компьютерной технике очень часто используется двоичная система счисления. Такую систему очень легко реализовать в электронике (полупроводниковые транзисторы и микросхемы), так как для неё требуется всего два устойчивых состояния (0 и 1).
 
Двоичная система счисления может быть непозиционной и позиционной системой. В ней используется две цифры: 0 и 1. В реальном устройстве это может быть реализовано присутствием какого-либо физического явления или его отсутствием. Например: есть электрический заряд или его нет, есть напряжение или нет, есть ток или нет, есть сопротивление или нет, отражает свет или нет, намагничено или не намагничено, есть отверстие или нет и т.п.
 
Мы уже знаем, как переводить числа в различные системы счисления. Посмотрим, как это происходит с двоичной системой счисления. Переведём число из двоичной системы счисления в десятичную.
 
<math>10101010_2 = 1 \cdot 2^7 + 0 \cdot 2^6 + 1 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 = 128 + 32 + 8 + 2 = 170</math>;
 
Вы это можете проверить на программе-калькуляторе (gcalctool в gnome, Kcalc в KDE, или калькулятор в Windows). Он умеет производить расчёты в двоичной, восьмеричной и шестнадцатиричной системах счисления. Теперь вы знаете, как он это проделывает. Если вы захотите посвятить свою жизнь программированию, то вам часто придётся работать со степенями двойки. Ниже представлена таблица:
{|class="standard"
!Степень||Значение
|-
|0||1
|-
|1||2
|-
|2||4
|-
|3||8
|-
|4||16
|-
|5||32
|-
|6||64
|-
|7||128
|-
|8||256
|-
|9||512
|-
|10||1024
|-
|11||2048
|-
|12||4096
|-
|13||8192
|-
|14||16384
|-
|15||32768
|-
|16||65536
|}
Произведём обратное преобразование. Чтобы преобразовать число в десятичном виде к двоичному, нам нужно будет делить всё время на два и смотреть на остаток от деления. Возьмём число 33.
 
* 33 : 2 = 16 остаток 1;
* 16 : 2 = 8 остаток 0;
* 8 : 2 = 4 остаток 0;
* 4 : 2 = 2 остаток 0;
* 2 : 2 = 1 остаток 0;
* 1 : 2 = 0 остаток 1;
 
Получили <math>100001_2</math>.
 
Возьмём число 55. Посмотрим, что получится.
 
* 55 : 2 = 27 остаток 1;
* 27 : 2 = 13 остаток 1;
* 13 : 2 = 6 остаток 1;
* 6 : 2 = 3 остаток 0;
* 3 : 2 = 1 остаток 1;
* 1 : 2 = 0 остаток 1.
 
Получили <math>110111_2</math>.
 
Ниже приведены ещё примеры со сложением, вычитанием, умножением и делением.
 
Сложение:
1001
1010
----
10011
Вычитание:
1110
0101
----
1001
Умножение:
1110
0101
----
1110
0000
1110
0000
-------
1000110
Деление:
1000110|101
101 -----
---- 0001110
111
101
---
101
101
---
00
 
'''Программа двоичного представления десятичного числа'''
''(Написана на [[w:Си (язык программирования)|Си]])''
 
<big><source lang="c">
#include <stdio.h>
#include <conio.h>
 
void dv(unsigned);
 
int main(int argc, char **argv)
{
unsigned x;
printf("Vvedite chislo > ");
scanf("%d", &x);
dv(x);
getch();
return 0;
}
 
void dv(unsigned x)
{
unsigned mask = 1, i;
mask <<= sizeof(unsigned) * 8 - 1;
for(i = 1; i <= sizeof(unsigned) * 8; i++)
{
printf("%c", x & mask ? '1' : '0');
x <<= 1;
if(!(i % 8))
printf(" ");
}
printf("\n");
}
</source></big>
 
== Система счисления с основанием е=2,718281828… ==