zabika.ru 1

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


Двоичная система использует две цифры: 0 и 1.

Десятичная – десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9

Шестнадцатеричная – 16 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E и F

Счёт до двадцати в трёх различных системах


двоичная

десятичная

шестнадцатеричная

0

0

0

1

1

1

10

2

2

11

3

3

100

4

4

101

5

5

110

6

6

111

7

7

1000

8

8

1001

9

9

1010

10

A

1011

11

B

1100


12

C

1101

13

D

1110

14

E

1111

15

F

10000

16

10

10001

17

11

10010

18

12

10011

19

13

10100

20

14



Операции в двоичной и шестнадцатеричной системах


Сложение




двоичная

шестнадцатеричная





Умножение




двоичная

шестнадцатеричная





Деление можно осуществлять в столбик, как и в десятичной системе. Однако это, как и в десятичной системе, включает в себя сложение и умножение в соответствующей системе, что уже само по себе непросто (для шестнадцатеричной системы – в особенности).
Перевод между системами

100101 в двоичной системе = 1*2^5 + 0*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 =

= 32 + 4 + 1 = 37 в десятичной

37 в десятичной =

37 / 2 = 18 + ½

18 / 2 = 9 + 0/2

9 / 2 = 4 + ½

4 / 2 = 2 + 0/2

2 / 2 = 1 + 0/2

1 / 2 = 0 + ½

Каждому второму слагаемому в правой части (это – остаток от деления) соответствует одна цифра двоичной системы: ½ соответствует 1, 0/2 – 0. Просматривая остатки снизу вверх получим ½ 0/2 0/2 ½ 0/2 ½ или 100101.

Перевод 10->16 производится аналогичным образом (деление десятичного числа на 16 и просмотр остатков).

44828/16 = 2801 + 12/16

2801/16 = 175 + 1/16

175/16 = 10 + 15/16

10/16 = 0 + 10/16

Просматривая остатки снизу вверх получим 10/16 15/16 1/16 12/16 или AF1C

Перевод 16->10 производится умножением каждого разряда на 16:

AF1C = A*16^3 + F*16^2 + 1*16^1 + C*16^0 = 10*16^3 + 15*16^2 + 1*16^1 + 12*16^0 = 44828
Перевод из двоичной системы в шестнадцатеричную более прост: двоичное число делится на куски по 4 цифры (справа налево), каждый кусок представляется в виде шестнадцатеричной цифры, которые потом сцепляются вместе.

101101100101111 = 101 1011 0010 1111 = 5 B 2 F

Обратно – то же самое: шестнадцатеричные цифры переводятся в двоичные числа и сцепляются обратно вместе.

Примем обозначение «0x» как указание на то, что число записано в 16-ричной системе счисления. То есть число 255 в десятичной – это 0xFF в шестнадцатеричной. Легко понять, что число шестнадцатеричное, если у него вместо некоторых цифр – буквы. А вот число 20 – это может быть как «20» в десятичной, так и «32» в шестнадцатеричной. Если записать 0x20, то сразу ясно, что это – 32, а если просто 20 – то это 20.


Двоичная логика



Двоичная логика работает с помощью утверждений, выражений и операций.

Утверждение может иметь два значения - либо «истинно» (true), либо «ложно» (false), потому логика и называется двоичной.

Операция – преобразование одних значений в другие.

Операция может быть бинарной (осуществляется над двумя значениями) или унарной (осуществляется над одним значением).

В бинарной логике тернарные операции не рассматриваются, хотя в более широком смысле они тоже существуют.

Значения, над которыми производится операция, называются операндами.

На столь ограниченном множестве значений существует конечное множество операций. Все они приведены в таблице. Здесь ‘op’ – обозначение некоторой операции.

Поставим в соответствие true единицу, а в соответствие false – ноль.


Названия операций\операнды

0 op 0

0 op 1

1 op 0

1 op 1




0

0

0

0

AND, И, конъюнкция, логическое умножение

0

0

0

1




0

0

1

0




0

0

1

1





0

1

0

0




0

1

0

1

XOR, Исключающее ИЛИ

0

1

1

0

OR, ИЛИ, дизъюнкция, логическое сложение

0

1

1

1




1

0

0

0




1

0

0

1




1

0

1

0




1

0

1

1




1

1

0

0




1

1

0

1




1

1

1

0




1

1

1

1

То есть 0 and 0 = 0; 0 and 1 = 0; 1 and 0 = 0; 1 and 1 = 1 и так далее.

Большинство операций не обозначено. Они существуют, но к программированию не имеют непосредственного отношения. Хотя, например, операцию с 10 строки можно назвать «равно», ток. она даёт «истину», если операнды равны, и «ложь», если они не равны.

Унарных операций ещё меньше:

Названия операций\операнды

op 0

op 1




0

0




0

1

NOT, НЕ, отрицание, инверсия

1

0




1

1

По аналогии остальные операции – это «утверждение лжи», «утверждение» и «утверждение истины», однако к программированию они также не имеют непосредственного отношения и здесь не рассматриваются.
Выражение – это набор операций над утверждениями.

Например, “A or B and not C”

Операции выполняются с определённым приоритетом. По аналогии с математикой, and имеет больший приоритет, чем or, а операция not имеет больший приоритет, чем and.

Таким образом, упомянутое выражение вычисляется в такой последовательности (операция в скобках – первая, как в математике): A or (B and (not C))


Допустим, A = 1; B = 0; C = 0;

Тогда A or B and not C = 1 or (0 and (not 0)) = 1 or (0 and 1) = 1 or 0 = 1

Алгоритмы


Алгоритм – непротиворечивая конечная последовательность действий.

Непротиворечивая – значит алгоритм нельзя понять неправильно, у него только одна интерпретация, он точен.

Конечная – значит алгоритм конечен сам, и его выполнение должно завершаться за конечное число шагов (само число шагов при этом может быть очень большим, это не оговаривается).

Последовательность – значит алгоритм выполняется последовательно, то есть – по порядку.

Пример алгоритма – умножение двоичных чисел (из раздела «Системы счисления»):

  1. для каждой цифры из второго двоичного числа, справа налево

  2. если цифра – 0, то

    1. вернуться к 1)

  3. если цифра – 1, то

    1. взять первое двоичное число, сдвинутое влево на столько разрядов, каков рассматриваемый разряд второго двоичного числа

    2. прибавить взятое число к результату

    3. вернуться к 1)

Алгоритм довольно кривой и содержит одну головоломную формулировку 3.a), но для человека вполне сойдёт.
Существуют различные способы описания алгоритмов.

Вышеописанный пример – это алгоритм в виде псевдокода.

Существует и другая форма представления алгоритмов – блок-схемы.
//TODO:подраздел про блоксхемы
Программа – изложение алгоритма (также говорят – «реализация алгоритма») в понятной компьютеру форме (в той форме, в которой компьютер может этот алгоритм выполнять).

Компьютер


Работа компьютера происходит примерно так:
Компьютер физически состоит из:

  1. Системная плата

  2. Процессор

  3. Оперативное Запоминающее Устройство (ОЗУ, т.е. оперативная память)

  4. Долговременное Запоминающее Устройство (ДЗУ, т.е. жёсткий диск)
  5. Устройство ввода (клавиатура, мышь)


  6. Устройство вывода (монитор, принтер)

  7. Платы расширения (видеокарта, сетевая карта, звуковая карта, и проч.)

Платы расширения, фактически, являются контроллерами для дополнительных устройств ввода/вывода (видеокарта – для монитора, сетевая карта – для сетевого кабеля, звуковая карта – для динамиков).

Системная плата содержит набор системной логики (не спрашивай меня, что это такое), различных контроллеров (как то – контроллер клавиатуры и мыши, контроллер ATA/SATA устройств).

Пункты 4) и 7), понятное дело, опциональны (теоретически).
С точки зрения архитектуры компьютер состоит из:

  1. Арифметическо-логическое устройство (Arithmetic and Logic Unit, ALU)

  2. Устройство управления (Control Unit, CU)

  3. Память(Memory)

  4. Система ввода/вывода (Input/Output system, I/O)

В современных компьютерах элементы 1, 2 (и частично 3 и 4) обычно объединены в одном устройстве – процессоре.

ALU занимается вычислениями (как видно из названия – арифметическими и логическими). Обычно набор операций, на которые способен ALU, ограничен базовыми операциями (сложение, вычитание, сравнение и т.д.). Более сложные операции выполняются как последовательность более простых операций (см. умножение двоичных чисел).

CU контролирует работу всего остального. В частности, оно управляет потоком команд и данных.

Память хранит команды и данные.

I/O позволяет получить команды и данные извне, а также вывести данные и команды из системы (т.е. вывести результат).

Элементы связаны между собой с помощью шин.
Процессор, как уже говорилось, состоит из АЛУ, УУ, памяти и I/O. Память процессора – это регистры и кэш. I/O процессора – это шина.

Регистровая память – это небольшое устройство для хранения данных, над которыми выполняется операция в данный момент, а также некоторых служебных данных. Регистровая память обладает просто диким быстродействием (самая быстрая память из всех существующих).


Кэш по объёму гораздо больше регистров, но он и медленнее. В кэш УУ записывает команды и данные, которые были выполнены и команды и данные, которые будут выполнены. Работа кэша связана с некоторым вероятностным процессом – УУ пытается угадать, какие команды должны будут выполняться в дальнейшем, и заранее поместить их в кэш, откуда они будут быстро поданы на регистры процессора, а также держать эти команды и данные в кэше, пока они нужны.

Оперативная память ещё больше по объёму и ещё медленнее, чем кэш. В оперативной памяти хранится всё, что нужно для работы компьютера.

Работа компьютера


Работа происходит примерно так:

УУ выбирает команду и данные из памяти (или из кэша), подаёт на АЛУ, АЛУ производит вычисление, УУ считывает данные с АЛУ и переписывает их в память, а потом всё повторяется для новой команды.

Где-то здесь УУ ещё успевает получать прерывания от различных устройств.

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

Биты, байты и прочие слова


Компьютер работает с минимальной единицей информации, называющейся «бит» (bit). Бит может принимать два значения – 0 или 1. Таким образом, один бит соответствует одному разряду в двоичной системе счисления. Физически биты кодируются как электрические импульсы различной интенсивности, как намагниченные участки магнитных дисков, как фазовые состояния электронных элементов и так далее.

Восемь бит организовываются в «байт» (byte). Очевидно, байту соответствует 8 разрядов двоичной системы счисления. Зная комбинаторику (или просто посчитав на пальцах), можно догадаться, что один байт может принимать 256 разных значений (различные комбинации 1 и 0) – от 0 до 255. Это считается как , где B – основание системы счисления, а n – количество разрядов. В нашем случае это , то есть – 256. Ещё раз заострю внимание на том, что «N разных значений» означает «от 0 до N-1».


Два байта составляют слово (word). Слово, очевидно, состоит из 16 бит и принимает 65536 разных значений - .

Два слова составляют двойное слово (double word, dword). Двойное слово, очевидно, состоит из 4 байт или 32 бит. Разных значений оно принимает уже дофига, порядка 4 миллионов -.

Два двойных слова составляют четверичное слово (quadriple word, qword). Четверичное слово состоит из 4 слов, 8 байт или 64 бит и принимает ОЧЕНЬ много разных значений - .

Числа


Легко догадаться, что 256 разных значений одного байта – это 256 чисел от 0 до 255, тут всё просто.

Со словом тоже несложно: слово – это число от 0 до 65535. Если записать в 16-ричной системе, то это будет от 0x0000 до 0xFFFF.

Двойное слово – от 0x00000000 до 0xFFFFFFFF.

И так далее.

Легко заметить, что все числа – положительные, либо ноль. А как быть с отрицательными?

Тоже просто: один бит будем считать не разрядом числа, а знаком. Если бит равен 0, то знак +; если бит равен 1, то знак -. Естественно, само число станет «меньше» в два раза (так как для представления собственно значения будет отводиться на 1 бит меньше), зато «пропавшая» половина «переедет» в отрицательный диапазон благодаря знаку, так что набор битов будет по-прежнему принимать N разных значений – просто половина этих значений будет отрицательной. Таким образом 1 байт принимает значения от -127 до 128 (-127..0..128 – всего 256 значений). Аналогично для более крупных единиц информации.

Дробные числа записываются сложнее. Дробное число представляется в виде , где N – само число, m – мантисса, p – основание, а n – показатель степени. В компьютерах p фиксировано и равно 2, поэтому число N записывается как пара значений – m и n . Для дробных чисел с одинарной точностью (single precision) форма записи такая:


1 бит на знак (0 = +1, 1 = -1), 8 бит на показатель степени, 23 бита на мантиссу. Показатель записывается в нормализованном виде путём прибавления к нему 127 (так как для показателя нету специального бита для обозначения знака, без этой уловки было бы невозможно записывать отрицательные показатели степени). Мантисса записывается как целое число, являющееся знаками после запятой в числе 1.xxxxxx.

Для примера: число 1 01111100 01000000000000000000000 - это

В русском языке для разделения целой и дробной частей используется запятая, в английском – точка. Поэтому у нас говорят «число с плавающей запятой», а у них - «число с плавающей точкой». Однако отныне и везде я буду писать дробные числа с точками, так как языки программирования обычно происходят от английского и понимают именно такое обозначение.

Битность и регистры


Компьютеры бывают 8-, 16-, 32- и 64-битные. Это определяется тем, каковы размеры регистров, и насколько большими числами они могут оперировать.


Ассемблер


Набор команд, понимаемых процессором, образует язык программирования, известный как Ассемблер (Assembler). Ассемблер – наиболее низкоуровневый (приближенный к физическим устройствам) язык, из всех доступных программисту. Его часто сокращённо называют «Асм» (по расширению файлов с ассемблерными командами - .asm).

Команды Асма – это указания для АЛУ и УУ в процессоре, управляющие вычислениями. Данные Асм берёт из памяти и/или регистров процессора. Каждый регистр имеет своё название: AX, BX, CX, DX и так далее. Ещё есть регистр флагов.

Размер регистра (количество информации, которое он может хранить) зависит от размерности системы. 8-битные системы имеют 8-битные регистры.