Позиционные системы счисления
Дата создания: 2010-03-05 07:29:41
Последний раз редактировалось: 2012-02-08 09:49:14
Тема данного урока не связана с созданием игр, но я всё же рекомендую с ней ознакомиться. Это позволит вам больше узнать о работе компьютера.
Сегодня мы более подробно ознакомимся с позиционными системами счисления, особенно с двоичной. Но раз бывают позиционные системы, то, стало быть, существуют и непозиционные? Так и есть. Примером непозиционной системы счисления является латинская. Вот несколько чисел из неё: I (1), V (5), II (2), III (3), X (10), XV (15). Далее речь будет идти только о позиционных системах счисления.
Для каждой системы счисления выбирается основание. Основание говорит, сколько цифр в данной системе счисления:
В десятичной системе (decimal; основание - 10) десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
В двоичной системе (binary; основание - 2) две цифры: 0, 1.
В шестнадцатеричной системе (hexadecimal; основание - 16) шестнадцать цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (10), B (11), C (12), D (13), E (14), F (15).
Числа состоят из последовательности разрядов. В каждом разряде записывается цифра. У каждого разряда есть своё имя. В десятичной системе счисления (начиная с младшего разряда) для целого числа: единицы (или разряд единиц), десятки, сотни, тысячи и т.д. Например, возьмём число 258. 8 - разряд единиц, 5 - разряд десятков, 2 - разряд сотен. Просто, не правда ли?
В двоичной системе счисления: разряд единиц, разряд двоек, разряд четвёрок, разряд восьмёрок и т.д. например, число 101: в самом младшем разряде (правая цифра) - в разряде единиц - расположена единица, в разряде двоек расположен ноль, в разряде четвёрок расположена единица.
В шестнадцатеричной системе счисления: разряд единиц, разряд числа 16, разряд числа 256 и т.д. Например, число af4: цифра 4 - в разряде единиц, f - в разряде числа 16, a - в разряде числа 256.
В позиционной системе счисления любое число в общем виде выглядит следующим образом:
xnam + xn-1am-1 ... x1a1 + x0a0
Где a - основание данной системы счисления, m - разряд, xn - значение в данном (n) разряде. Три примера для различных систем счисления (десятичной, двоичной, шестнадцатеричной):
3892 = 3*103 + 8*102 + 9*101 + 2*100 1101 = 1*23+1*22+0*21+1*20 AB3 = A*162 + B*161+3*160
Преобразования чисел между различными системами счисления
Важно: материал этого и следующего раздела может показаться сложным. Пожалуйста, внимательно прочтите оба раздела (до раздела "Кодирование данных...") и обязательно выполните рекомендацию из предпоследнего абзаца раздела "Арифметические действия...".
Самые простые преобразования - между двоичной и шестнадцатеричной системами счисления, так как основание шестнадцатеричной системы равно основанию двоичной в четвёртой степени: 16 = 24. Один разряд шестнадцатеричного числа состоит из четырёх разрядов двоичного. Сначала нужно выучить значения первых шестнадцати двоичных и шестнадцатеричных чисел:
0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F
Теперь можно взять любое двоичное число, разбить его по четыре разряда и в соответствии с вышеприведённой таблицей получить шестнадцатеричное число. Для примера возьмём два 32-ухбитных числа:
1010 1100 0100 0011 1111 1001 0110 0001 = AC43F960 или: 17FA20B5 = 0001 0111 1111 1010 0010 0000 1011 0101
Здесь главное заучить первые шестнадцать чисел, дальше просто. Теперь о преобразовании в десятичную систему счисления. Для этого все цифры числа домножаются на разряд и суммируются:
bin dec
1101001 = 105
26 25 24 23 22 21 20
64 32 16 8 4 2 1 // разряды
1 1 0 1 0 0 1 = 1*64 + 1*32 + 0*16 + 1*8 + 4*0 + 2*0 + 1*1 = 105
//----------------------
hex dec
1A3F = 6719
163 162 161 160
4096 256 16 1
1 A 3 F = 1*4096 + 10*256 + 3*16 + 15*1 = 6719
Преобразования из десятичной системы происходят немного не так. Сначала нужно записать разряды той системы счисления, в которую будет преобразовываться число. Причём самый старший разряд должен быть больше числа. После этого старший разряд можно отбросить и работать с оставшимися. Затем нужно делить число на разряд. Целую часть нужно записать в текущий разряд, а остаток делить на младший разряд:
dec bin 148 = 10010100 256 128 64 32 16 8 4 2 1 // разряды системы счисления 1 0 0 1 0 1 0 0 // число 148 / 128 = 1 | 20 // преобразование 20 / 64 = 0 | 20 20 / 32 = 0 | 20 20 / 16 = 1 | 4 4 / 8 = 0 | 4 4 / 4 = 1 | 0 //---------------------- dec hex 8932 = 22E4 65536 4096 256 16 1 // разряды системы счисления 2 2 E 4 // преобразованное число 8932 / 4096 = 2 | 740 // преобразование 740 / 256 = 2 | 228 228 / 16 = E | 4
Арифметические действия в позиционных системах счисления
С детства мы используем десятичную систему счислениям. В первых классах (во втором, по-моему?) мы изучаем таблицу умножения для десятичной системы.
Во всех позиционных системах счисления для арифметических операций действуют одни и те же правила. Конечно, умножение в шестнадцатеричной системе счисления будет казаться нам сложнее, но это потому, что мы не привыкли к таблице умножения (её без проблем можно составить самостоятельно) и таблице сложения (да, есть и такая, только для десятичной системы она слишком проста и не изучается) для этой системы. Рассмотрим несколько примеров. Надеюсь, вы не забыли как складывать, вычитать, умножать и делить числа:
// сложение и вычитание: 11 . A38FC 10110 + DE1 - 101 =----- =----- A46DD 10001 // умножение/деление двоичных чисел: 10110|10 10110 -10 |---- x 11 11 |1011 ----- -10 10110 10 10110 -10 =------- 0 1000010 // умножение/деление шестнадцатеричных чисел: 22cd8|ce F7CA -19c |--- x B9 90d |2b4 ---- -8da 8B61A 338 AA5AE -338 =------ 0 B310FA
Настоятельно рекомендую попрактиковаться в арифметических действиях в разных системах счисления. Хотя бы в течении недели ежедневно выполняйте несколько операций (для шестнадцатеричной системы понадобится составить таблицы сложения и умножения): берёте пару чисел в десятичной системе счисления, переводите в двоичную/шестнадцатеричную и выполняете несколько действий. Для мозга очень полезная разминка. Недели через две почувствуете, что лучше начали соображать.
Почему мы рассмотрели именно эти системы счисления: десятичную, двоичную и шестнадцатеричную? Всё очень просто: десятичную систему мы используем постоянно, и нам она понятнее; двоичная система используется компьютером; а шестнадцатеричная система позволяет сократить двоичные числа, так как основание шестнадцатеричной системы является степенью основания двоичной.
Кодирование данных и двоичные числа
Практически любую информацию можно хранить в виде нулей и единиц. Но для этого её нужно каким-то образом закодировать. Мы уже встречались с кодированием изображений в формате bmp. Изображение кодируется исходя из количества каналов на каждый пиксель и количества бит на канал. Или, например, текст, который вы сейчас читаете, закодирован с помощью кодировки Windows-1251. И если, например, в следующем слове вы видите выражение приветствия: "Привет" - то для компьютера это последовательность из 48-и нулей и единиц (шесть байт).
Разве это не потрясающе: текст, графика, видео, музыка, стереоскопические изображения (их поддержка появилась в последних версиях DirectX) - и всё это создаётся всего лишь из двух цифр! Кстати, информация, закодированная с помощью цифр, и устройства, хранящие информацию в виде цифр, называются цифровыми. В противоположность цифровым устройствам, аналоговые устройства хранят информацию не в виде цифр, а каким-то другим образом. Например, виниловые пластинки, магнитные ленты, ртутные/спиртовые градусники, неэлектронные весы.
Двоичная цифра (ноль или единица) называется битом (от binary digit - двоичная цифра). Можно сказать, что бит - наименьшая единица информации.
Отрицательные числа в двоичной системе
Раз двоичная система счисления имеет настолько большое значение, то с ней нужно познакомиться подробнее. В одном из следующих уроков мы узнаем как в двоичной системе хранятся дробные числа. А сейчас рассмотрим системы представления отрицательных чисел. В примерах будем использовать восьмибитные числа.
1. Система представления отрицательных чисел со знаком. В данном случае крайний левый бит хранит знак: плюс - ноль, минус - единица. За исключением бита со знаком, отрицательные числа выглядят точно также, как и положительные. В данной системе два нуля : +0 - 00000000, -0 - 10000000.
2. Система дополнения до единицы (one's complement). Крайний левый бит хранит знак. Здесь также два нуля. Для хранения отрицательного числа в данной системе нужно поменять все биты положительного числа на противоположные.
3. Система дополнения до двух (two's complement). Знак хранится в левом бите. Но здесь уже только один ноль: 00000000. В данной системе число 10000000 будет равно -128. Обратите внимание, что в данной системе, отрицательных чисел больше (на одну) чем положительных. Теперь вопрос, в какой системе хранятся числа в типах: int, char, long?
Образование отрицательного числа в системе дополнения до двух происходит в два этапа: сначала биты меняются на противоположные (как в дополнении до единицы), а затем к получившемуся результату прибавляется единица. Два примера:
Положительное Дополнение Дополнение
число Со знаком до единицы до двойки
00000001 10000001 11111110 11111111 // -1, кроме первого числа
00001010 10001010 11110101 11110110 // -10, кроме первого числа
Возьмите несколько чисел в десятичной системе, преобразуйте их в двоичную и найдите отрицательные числа в различных системах представления знака.
Теперь проиллюстрируем дополнение до единицы и до двойки кодом:
int a = 1; // два целых 32-ухбитных числа со знаком int b = 1; a = ~a; // отрицательное число в системе дополнения до единицы b = ~b + 1 // отрицательное число в системе дополнения до двойки
Операция поразрядного логического НЕ ~ (символ называется: тильда, клавиша с этим символом расположена слева вверху на клавиатуре, там где буква ё) меняет все биты в числе на противоположные. Интересный момент - все операции вычитания для процессора выглядят вот так:
int a = 325; int b = 239; int c = 0; c = a + (~b + 1); // обычно мы писали: c = a - b;
На сегодня всё.