Содержание.
ГЛАВА 1. Введение
1.1. Система обозначений 19
1.2. Система команд и модель оценки времени выполнения команд 23
Время выполнения 28
Упражнения 30
ГЛАВА 2. Основы
2.1. Манипуляции младшими битами 31
Расширенные законы де Моргана 33
Проверка выполнимости справа налево 33
Новое применение 35
2.2. Сложение и логические операции 36
2.3. Неравенства с логическими и арифметическими выражениями 38
2.4. Абсолютное значение 39
2.5. Среднее двух целых 39
2.6. Распространение знака 40
2.7. Знаковый сдвиг вправо на основе беззнакового сдвига 40
2.8. Функция sign 41
2.9. Трехзначная функция сравнения 42
2.10. Перенос знака 42
2.11. Декодирование поля "0 означает 2**n" 43
2.12. Предикаты сравнения 43
Команды сравнения и бит переноса 47
Вычисление отношений 48
2.13. Обнаружение переполнения 49
Знаковое сложение и вычитание 49
Установка переполнения при знаковом сложении и вычитании 51
Беззнаковое сложение/вычитание 52
Умножение 53
Деление 55
2.14. Флаги условий после сложения, вычитания и умножения 58
2.15. Циклический сдвиг 59
2.16. Сложение/вычитание двойных слов 60
2.17. Сдвиг двойного слова 61
2.18. Сложение, вычитание и абсолютное значение многобайтовых величин 62
2.19. Функции doz, max, min 63
2.20. Обмен содержимого регистров 68
Обмен соответствующих полей регистров 68
Обмен двух полей одного регистра 69
Условный обмен 70
2.21. Выбор среди двух или более значений 70
2.22. Формула булева разложения 73
2.23. Реализация команд для всех 16 бинарных булевых операций 75
Исторические примечания 77
Упражнения 77
ГЛАВА 3. Округление к степени
3.1. Округление к кратному степени 281
3.2. Округление к ближайшей степени 282
Округление в меньшую сторону 83
Округление в большую сторону 84
3.3. Проверка пересечения границы степени 285
Упражнения 87
ГЛАВА 4. Арифметические границы
4.1. Проверка границ целых чисел 89
4.2. Определение границ суммы и разности 92
Знаковые числа 94
4.3. Определение границ логических выражений 96
Знаковые границы 100
Упражнения 101
ГЛАВА 5. Подсчет битов
5.1. Подсчет единичных битов 103
Сумма и разность количества единичных битов в двух словах 110
Сравнение степени заполнения двух слов 111
Подсчет единичных битов в массиве 111
Применение 117
5.2. Четность 118
Вычисление четности слова 119
Добавление бита четности к7-битовой величине 121
Применение 121
5.3. Подсчет ведущих нулевых битов 122
Методы с плавающей точкой 127
Сравнение количества ведущих нулевых битов двух слов 129
Связь с логарифмом 129
Применения 130
5.4. Подсчет завершающих нулевых битов 130
Применение 137
Упражнения 140
ГЛАВА 6. Поиск в слове
6.1. Поиск первого нулевого байта 141
Некоторые простые обобщения 145
Поиск значения из заданного диапазона 146
6.2. Поиск строки единичных битов заданной длины 147
6.3. Поиск наидлиннейшей строки единичных битов 150
6.4. Поиск кратчайшей строки единичных битов 152
Упражнения 153
ГЛАВА 7. Перестановка битов и байтов
7.1. Реверс битов и байтов 155
Обобщенный реверс битов 160
Современные методы реверса битов 161
Увеличение обращенного целого числа 163
7.2. Перемешивание битов 165
7.3. Транспонирование битовой матрицы 167
Транспонирование битовой матрицы размером 32?32 171
7.4. Сжатие, или Обобщенное извлечение 176
Использование команд вставки и извлечения 181
Сжатие влево 182
7.5. Расширение, или Обобщенная вставка 182
7.6. Аппаратные алгоритмы сжатия и расширения 183
Сжатие 183
Расширение 185
7.7. Обобщенные перестановки 187
7.8. Перегруппировки и преобразования индексов 191
7.9. АлгоритмLRU 192
Упражнения 195
ГЛАВА 8. Умножение
8.1. Умножение больших чисел 197
8.2. Старшее слово 64-битового произведения 200
8.3. Преобразование знакового и беззнакового произведений одно в другое 200
Беззнаковое произведение из знакового 201
8.4. Умножение на константы 201
Упражнения 205
ГЛАВА 9. Целочисленное деление
9.1. Предварительные сведения 207
9.2. Деление больших чисел 210
Знаковое деление больших чисел 215
9.3. Беззнаковое короткое деление на основе знакового 215
Использование знакового длинного деления 215
Использование знакового короткого деления 216
9.4. Беззнаковое длинное деление 219
Аппаратный алгоритм сдвига и вычитания 219
Использование короткого деления 222
9.5. Деление двойных слов из длинного деления 224
Беззнаковое деление двойных слов 225
Знаковое деление двойных слов 228
Упражнения 229
ГЛАВА 10. Целое деление на константы
10.1. Знаковое деление на известную степень 2 231
10.2. Знаковый остаток от деления на известную степень 2 232
10.3. Знаковое деление и вычисление остатка для других случаев 233
Деление на3 233
Деление на5 235
Деление на7 235
10.4. Знаковое деление на делитель, не меньший 2 236
Алгоритм 238
Доказательство пригодности алгоритма 239
Доказательство корректности произведения 240
10.5. Знаковое деление на делитель, не превышающий–2 243
Для каких делителей m(–d) ?–m(d)? 245
10.6. Встраивание в компилятор 246
10.7. Дополнительные вопросы 249
Единственность 249
Делители с лучшими программами 250
10.8. Беззнаковое деление 253
Беззнаковое деление на3 253
Беззнаковое деление на7 254
10.9. Беззнаковое деление на делитель, не меньший 256
Беззнаковый алгоритм 257
Доказательство пригодности беззнакового алгоритма 257
Доказательство корректности произведения в случае беззнакового деления 258
10.10. Встраивание в компилятор при беззнаковом делении 258
10.11. Дополнительные вопросы(беззнаковое деление) 260
Делители с лучшими программами(беззнаковое деление) 260
Использование знакового деления вместо беззнакового и наоборот 261
Более простой беззнаковый алгоритм 262
10.12. Применение к модульному делению и делению с округлением к меньшему значению 263
10.13. Другие похожие методы 263
10.14. Некоторые магические числа 265
10.15. Простой код на языке программирования Python 266
10.16. Точное деление на константу 266
Вычисление мультипликативного обратного по алгоритму Евклида 268
Вычисление мультипликативного обратного по методу Ньютона 271
Некоторые мультипликативные обратные 273
10.17. Проверка нулевого остатка при делении на константу 274
Беззнаковое деление 275
Знаковое деление, делитель ?2 276
10.18. Методы, не использующие команды умножения со старшим словом 278
Беззнаковое деление 278
Знаковое деление 286
10.19. Получение остатка суммированием цифр 288
Беззнаковый остаток 289
Знаковый остаток 293
10.20. Получение остатка путем умножения и сдвига вправо 295
Беззнаковый остаток 295
Знаковый остаток 299
10.21. Преобразование в точное деление 301
10.22. Проверка времени выполнения 302
10.23. Аппаратная схема для деления на 3 303
Упражнения 304
ГЛАВА 11. Некоторые элементарные функции
11.1. Целочисленный квадратный корень 305
Метод Ньютона 305
Бинарный поиск 309
Аппаратный алгоритм 310
11.2. Целочисленный кубический корень 313
11.3. Целочисленное возведение в степень 314
Вычислениеxn бинарным разложениемn 314
2n в Fortran 315
11.4. Целочисленный логарифм 316
Целочисленный логарифм по основанию 2 317
Целочисленный логарифм по основанию 10 317
Упражнения 323
ГЛАВА 12. Системы счисления с необычными основаниями
12.1. Основание– 2 325
12.2. Основание– 1+i 332
12.3. Другие системы счисления 335
12.4. Какое основание наиболее эффективно 335
Упражнения 336
ГЛАВА 13. Код грея
13.1. Код Грея 337
13.2. Увеличение чисел кода Грея 339
13.3. Отрицательно-двоичный код Грея 341
13.4. Краткая история и применение 341
Упражнения 343
ГЛАВА 14. Циклический избыточный код
14.1. Введение 345
Основы 345
14.1. Теория 347
14.3. Практика 349
Аппаратное обеспечение 351
Программная реализация 353
Упражнения 356
ГЛАВА 15. Коды с коррекцией ошибок
15.1. Введение 357
15.2. Код Хэмминга 358
КодSEC-DED 360
Минимально необходимое количество проверочных битов 362
Заключительные замечания 362
15.3. Программная реализация SEC-DED для 32 информационных битов 364
15.4. Общее рассмотрение задачи коррекции ошибок 369
Расстояние Хэмминга 370
Основная задача теории кодирования 372
Сферы 374
Упражнения 379
ГЛАВА 16. Кривая Гильберта
16.1. Рекурсивный алгоритм построения кривой Гильберта 383
16.2. Преобразование расстояния вдоль кривой Гильберта в координаты 385
16.3. Преобразование координат в расстояние вдоль кривой Гильберта 393
16.4. Увеличение координат кривой Гильберта 395
16.5. Нерекурсивный алгоритм генерации кривой Гильберта 398
16.6. Другие кривые, заполняющие пространство 398
16.7. Применения 399
Упражнения 400
ГЛАВА 17. Числа с плавающей точкой
17.1. Формат IEEE 401
17.2. Преобразование чисел с плавающей точкой в целые и обратно 404
17.3. Сравнение чисел с плавающей точкой с использованием целых операций 408
17.4. Программа приближенного вычисления обратного к квадратному корню 410
17.5. Распределение ведущих цифр 413
17.6. Таблица различных значений 415
Упражнения 417
ГЛАВА 18. Формулы для простых чисел
18.1. Введение 419
18.2. Формулы Вилланcа 421
Первая формула 421
Вторая формула 422
Третья формула 423
Четвертая формула 424
18.3. Формула Вормелла 424
18.4. Формулы для других сложных функций 425
Упражнения 431
Ответы к упражнениям Глава 1 - 18
Приложения
Приложение А. Арифметические таблицы для 4-битовой машины
Приложение Б. Метод Ньютона
Приложение В. Графики дискретных функций
В.1. Графики логических операций над целыми числами 489
В.2. Графики для сложения, вычитания и умножения 491
В.3. Графики функций, включающих деление 493
В.4. Графики функций сжатия, обобщенного упорядочения и циклического сдвига влево 494
В.5. Графики некоторых унарных функций 496
Список технической литературы 501
Добавить комментарий