Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 41
Текст из файла (страница 41)
В случае использования 16 битов зто осуществляется путем вычитания целого положительного числа в шестнадцатеричной форме из ГГГГ и последующего прибавления 1. Как и раньше, для преобразования отрицательного числа обратно в его положительного двойника выполняем операцию дополнения, вычитая его из а затем прибавляя 1. ПРИМЕР 6.47. Найти представление в шестнадцатеричной системе счисления отрицания шестнадцатеричного числа 78Е с использованием 16 бит. Сначала заменим запись числа на 16-битовое шестнадцатеричное число 078Г.
Затем вычтем 078Г из ГГГГ, получив Г870, и далее прибавляем 1. В итоге получаем представление Г871. П ПРИМЕР 6.48. Найти 16-битовое представление в шестнадцатеричной форме числа — 1158ш. Поскольку 11581о = 486ш = 0486, представленное в 16-битовой шестнадцатеричной форме, вычитаем 0486 из ЕГГЕ, получая ЕВ79, после чего, прибавляя 1, получаем ЕВ7А. Следовательно, 16-битовое шестнадцатеричное представление числа — 1158го есть ГВ7А. и Сложение чисел фиксированной длины со знаком на основе двоичного или шестнадцатеричного представления ничем не отличается от обычного сложения двоичных и шестнадцатеричных чисел, за исключением того, что если сумма порождает дополнительный разряд, тогда первый разряд удаляется.
Например, если 0111 и 1011 складываются как двоичные числа; 0111 1011, [1) 0010 то цифра 1 слева удаляется. Если шестнадцатеричные числа со знаком ГГ14 и ОГ1А складываются как шестнадцатеричные: ГГ14 ОГ1А, [1) ОЕ2Е то цифра 1 слева также удаляется. Если попытаться сложить 7Г14 и 6Е23, то получаем 7Г14 6Е23 ЕР37 т.е. сложив два положительных числа, получили отрицательное число.
В таком случае говорят, что имеет место переполнение. Значение суммы слишком велико 234 ГЛА8А о. Алгоритмы и рекурсия для представления с использованием 16 бит. Числа со знаком, выражаемые с использованием 16 двоичных разрядов или 4 шестнадцатеричных разрядов, должны находиться между -32768 и 32767. В десятичной арифметике, чтобы вычесть 25 из 75, к 75 прибавляют — 25.
Во многих учебниках пишут: "измените знак вычитаемого [того числа, которое вычитается] и выполните сложение". При сложении чисел со знаком необходимо действовать таким же образом. При вычитании одного целого числа из другого находим двоичное дополнение числа, которое нужно вычесть, и производим сложение. Например, для нахождения разности 01010110 — 01110001 мы сначала находим двоичное дополнение числа 01110001, которое равно 10001111, после чего выполняем сложение: 01010110 + 10001111 .
11100101 Как и следовало ожидать, результат — отрицательное число. Используя тот же самый подход при решении следующей задачи: 01010001 — 11101001, мы сначала находим двоичное дополнение числа 11101001, которое равно 00010111, после чего выполняем сложение; 01010001 + 00010111 . 01101000 В данном случае отрицательное число вычиталось из положительного, поэтому отрицательное число мы заменили положительным и произвели сложение. ПРИМЕР 5.49. Вычесть 56 из 23, используя 8-битовые числа со знаком. Поскольку 56 = 00111000 и 23 = 00010111, имеем 00010111 — 00111000 .
Сначала находим двоичное дополнение числа 00111000, которое равно 11001000, а затем выполняем сложение: 00010111 + 11001000, 11011111 Так как двоичным дополнением числа 11011111 является 00100001, которое равно 33, число 11011111 равно -33. 0 РКЗЯЕЛ 5.7. Числа со знаком 235 Сначала находим двоичное дополнение числа 1САО, которое равно ЕЗ5Г, а затем выполняем сложение: ОЕ1Е + Е360 . Г17Е Поскольку двоичным дополнением числа Г1Е является ОЕ82 и ОЕ82 = 37141о, то 3614 — 7328 = — 3714. П ° УПРАЖНЕНИЯ 1. Найдите двоичное дополнение приведенных ниже 8-битовых чисел ной форме: а) 01110110; б) 10110101; в) 00110111; г) 11101011.
2. Найдите двоичное дополнение приведенных ниже 8-битовых чисел ной форме: а) 01100100; б) 11011001; в) 00111011; г) 10010000. 3. Выразите следующие десятичные числа как 8-битовые двоичные знаком: а) 73; б) — 101; в) — 37; г) — 14.
4. Выразите следующие десятичные числа как 8-битовые двоичные знаком; а) 48; б) — ЗЗ; в) — 58; г) — 114. 5. Выполните следующие операции, используя 8-битовые двоичные знаком: 10110100 00110100 а) + 01110010; б) + 01001010; в двоич- в двоич- числа со числа со числа со 00110101 в) — 01110110 00110101 г) — 01110110 операции, используя 8-битовые двоичные числа со 5. Выполните следующие знаком: 11001001 а) + 01011110; 00101001 б) + 01010011 01011100 в) — 01110111 01101101 г) — 01111000 ПРИМЕР 5.50. Вычесть 7328 из 3614, воспользовавшись 16-битовыми шестнадцатеричными числами со знаком. Поскольку 73281о = 1САОга и 3614 = Е1Еми имеем ОЕ1Š— 1САО . 236 ГЛА8А 5.
Алгоритмы и рекурсия Превратите следующие числа в 8-битовые двоичные числа со знаком и выполните указанные операции: 43 а) +28; 43 в) — 67 86 г) — 73 8. Превратите следующие числа в 8-битовые двоичные числа со знаком и вы- полните указанные операции: 29 а) +61; 34 б) — 56 13 в) — 87 22 г) — 98 9. Найдите двоичное дополнение следуюших чисел со знаком, выраженных в шестнадцатеричной форме: а) 723А; б) АВ20; в) ГА12; г) 23ВС.
женных в шестнадцатеричной форме: а) 23СГ; б) 1В5С; в) ГР13; г) 1020. 11. Выразите следуюшие десятичные числа как 16-битовые числа со знаком в шестнадцатеричной форме: а) 270; б) — 893; в) -17; г) — 9872 12. Выразите следующие десятичные числа как 8-битовые двоичные числа со знаком; а) 48; б) — 237; в) -8858; г) — 12499 13. Выполните следующие операции, используя 16-битовые числа со знаком в шестнадцатеричной форме: ЗС14 а) + 89АС; С12г' б) + 359А; В127 в) — С1АВ 34С5 г) — ГГ12 14.
Выполните следующие операции, используя 16-битовые числа со знаком в шестнадцатеричной форме: 4713 а) + 0г23; 5379 б) + ЕА12; 10. Найдите двоичное дополнение приведенных ниже чисел со знаком, выра- РАЗДЕЛ 5.В. ДальнеВшее изучение матриц 237 37В4 в) — АА44 С129 г) — В48А шестнадцатеричные числа со зна- 1639 + 3926 8836 в) — 19923 994 ) - 1713 шестнадцатеричные числа со зна- 778 — 569 19237 г) — 18 13 в) — 87 Детерминант является важной функцией, отображающей множество матриц с элементами из множества действительных чисел во множество действительных чисел.
Детерминант используется при решении систем уравнений (метод Крамера), а также при определении обратной матрицы (если она существует). Пусть дана п х и матрица Аы Ага . А1„ Аш Агг Аг А~1 Апг Аип Символом А,, обозначим матрицу размера (и — 1) х (и — 1), полученную удалением в исходной матрице 1-ой строки и ~-го столбца.
ПРИМЕР 5.51. Пусть Аы А1г Тогда Аы = [Агг], Агг = [Ащ], Аг1 = [Агг] и Агг = [Аы]. 15. Переведите следующие числа в 16-битовые ком и выполните указанные операции: 936 а) + 258; б) 16. Переведите следующие числа в 16-битовые ком и выполните указанные операции: 829 а) + 1499; б) 17. Найдите диапазон целых чисел, который знаком с использованием 32 бит. 18. Найдите диапазон целых чисел, который знаком с использованием 64 бит. 5.8.
ДАЛЬНЕЙШЕЕ ИЗУЧЕНИЕ МАТРИЦ может быть выражен числами со может быть выражен числами со 238 ГЛАВА 5. Алгоритмы и рекурсия ПРИМЕР 5.52. Пусть А= [ А11 Ага А1з Агг Агг Агз Азг Азг Азз Тогда А Агг Агз А Аы Агз А Агг Агз П ОПРЕДЕЛЕНИЕ 5.53. Детерминант матрицы размера и х и А11 А1г . А1, Агг Агг ' ' ' Агп Ап1 Апг Апп обозначается через с1ет(А), (А! или А11 А1г . А1 Агг Агг Аг Ап1 Апг Апп и определяется следуюшим образом: а) если п = 1, то с(ет(А) = ~А11~ = Аы, и б) если п ) 2, то бес(А) = 2 А1,( — 1)1+э дет(А1 ).
1=1 Пусть М, = 11ес(А11). Число М, называется минором элемента А1, а число С1 = ( — 1)'пубет(А1 ) — алгебраическим дополнением элемента Аьп Следои и вательно, дет(А) = 2; А1,( — 1)'еуде1(А1 ) = 2; А, Сгсь 1п1 1=1 Обратите внимание, что в приведенном выше определении ~А11~ не является абсолютным значение Аы, хотя обозначение кажется таким же. Давайте теперь составим алгоритм для вычисления детерминанта. Прежде всего отметим, что детерминант порядка и х и определен через детерминанты порядка (и — 1) х (и — 1). Здесь мы сталкиваемся с примером рекурсивного алгоритма. В дальнейшем мы рассмотрим алгоритмы такого типа более подробно.
Процедура вычисления детерминанта имеет следуюший вид: РАЗДЕЛ 5.8. Дальнейшее озучение метроц 239 Ап А1г то де1(А) = Ап ~Агг~ — Ага. )Аг~( = Ап Агг — Азг. Агп Если Ап Азг А1з А = Агз Агг Агз Азз 4зг Азз то Агг Агз ~ 4 ~ Агг Агз 1 Аг1 Агг 1 Азг Азз 1 ~ Аз1 Азз 1г ' ~ + зз. Аз1 Азг ПРИМЕР 6.64. Пусть А = ~ ~. Тогда 12 31 ~1 2~' с1ес(А) = =2~2!+3( — (Ц) =2 х 2 — 3 х 1=1.
2 3 В общем случае, если А = ~ ~, то бе1(А) = ас~ — Ьс. (а Ь1 ~ с 1 2 О 1 1 2 . Тогда 3 О 1 ПРИМЕР 6.66. Пусть А = 1 2 О 1 1 2 3 О 1 с$ет(А) = Процедура Детерминант(А, и): Цикл по 1 от 1 до и: Если и = 1, то дет(А) = ~Ап~ = Ап', Если и > 2, то с(ет(А) = О; Цикл по г' от 1 до и: Значение деФ(А) заменить на без(А) + АП(-1)'+ЗДетерминант(А1з, и — 1); Конец цикла; Конец цикла; Конец процедуры.
Поскольку детерминант (А,и) определен через детерминанты (А1,и — 1), для вычисления детерминанта (А,и) прежде необходимо определить детерминан- ты (А~, и — 1). Многие компьютерные программы обладают свойством "вызывать" саму себя. Это дает возможность написать компьютерную программу, очень похо- жую на приведенную выше процедуру. В более полном объеме этот вопрос будет рассмотрен в последующих разделах. Следовательно, если 240 ГЛАВА 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
