Керниган, Ричи. Язык С.
Страуструп. С++
Таненбаум. Современные операционные системы.
Т. Кормен,
Ч. Лейзерсон, Р. Ривест, К.
Штайн — Алгоритмы. Построение и анализ.
Кнут. Искусство программирования. 3
том.
Препарата, Шеймос.
Вычислительная геометрия.
Бит = наименьшая ячейка памяти в ЭВМ
Байт = наименьшая ячейка, у которой
есть адрес
Линейная адресация
Физическая память/Виртуальная память
Слово
Оперативная память (по адресу) +
Регистры (по именам)
mov RX,DX
Целые числа без знака.
Позиционная система отсчета:
(xn-1,xn-2,…,x0)k где xi – цифра в k-ичной
системе отсчета
(xn-1,xn-2,…,x0)k = x = ∑i=0n-1 xi*ki
16-ричная цифра∈ {0,1,2,..,9,a,b,c,d,e,f}
байт = две 16-ричные цифры
0xff = (1111 1111)2
k=2
2-байтовое целое число:
Big-endian: в начале – старший байт: x15,…,x8, ,x7,…,x0 – IBM
Little-endian: в начале – младший байт: x7,…,x0, x15,…,x8
– Intel (+AMD)
Целые числа со знаком
(xn-1,xn-2,…,x0)2
Старший бит = знак (1=минус, 0=плюс)
1)Прямое представление
-1 = (1000 0001)
2)Обратный код
-1=(1111 1110)
3)Дополнительный код:
x>0:
-x=?=
x=3
=?> -x
x=(0000 0011)
1. Инверсия
(1111
1100)
2.+=1
-3=(1111 1101)
(1000
0000)=?=-x (x>0)
x=?
2.-=1
1000
0000-
0000
0001
------------
0111 1111
1.~ 0111 1111
1000
0000=128
(1000 0000)=-128
1-байтовые целые ∈ {-128,…,127}
k-битовые
целые ∈ {-2k-1,…,2k-1-1}
Любая последовательность бит в доп.коде
соответствует целому числу.
Теорема. Дополнительный код = представление чисел в
кольце вычетов по модулю 2k, где k – к-во бит в представлении числа.
Д-во.
x>0
рассмотрим -x=?=2k-x
1.Инверсия x = (1111 1111)-(x7,…,x0) = ~x
(2k-1)-x
1 0000 0000-1
2.+=1
(2k-1)-x +1 = 2k-x
ч.т.д.
Следствие. Результаты сложения, вычитания, умножения не
зависят от представления числа (доп.код/число
без знака).
-3 + -3=
1111 1101
1111 1101
-------------
(1)1111 1010
=-x
x=?
2.
1111 1010
- 1
----------
1111
1001
1.~ 1111 1001 = 0000 0110=2+4=6
-3 + -3= -6
1111
1101
0000 0011
При работе с целыми числами не отслеживаются переполнения.
(-1)/2=
(1111 1111)≫1=(1111
1111)
int x=…;
for(;x!=0;x≫=1)
{
}
(0111 1111)≫1=(0011
1111)
0100
0000
0100
0000
-----------
1000
0000