Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 39
Текст из файла (страница 39)
Двоичные и шестнадцатеричные числа 223 и делим 1944 на 256. Поскольку частное от деления равно 7, а остаток равен 152, помешаем 7 в третий столбец: 8 1 7 66536 4096 256 16 1 164 16з 16з 16г 16о и делим 152 на 16. Частное от деления равно 9, остаток равен 8, поэтому помешаем 9 в четвертом участке, а 8 — в последнем столбце: 8 1 7 9 8 66536 4096 256 16 1 164 16з 16з 16г 16о 1. Разделить п на 16, получив частное 9г и остаток тг.
2. Разделить 91 на 16, получив частное дз и остаток тз. 3. До тех пор, пока дь не равно О, делить дь на 16, получая частное дьч.з и остаток гьч.ы 4. Если д„ = О, то (г„г„ ,. гзгзгз)з — — п1о. ПРИМЕР 5.36. Снова рассмотрим преобразование 530328 в шестнадцатеричное число. Поскольку 530328 = 16(33145) + 8, то 9з = 33145 и г1 = 8.
Поскольку 33145 = 16(2071) + 9, то дз = 2071 и гз = 9. Поскольку 2071 = 16(129) + 7, то яз — 129 и гз = 7. Поскольку 129 = 16(8) + 1, то 94 = 8 и г4 = 1. Следовательно, гз = 8 и 530328ш = 81798|а. П Рациональное число в десятичной системе счисления, например, 326.149, представляется в виде 3(10)' + 2(10)' + 6(10)' + Ц10)-' + 4(10)-' + 3(10)-', или 3 2 6 1 4 3 (10)з (10)' (10)о (10) 1 (10) з (10) Аналогичным образом рациональное число в двоичной системе счисления, например, 1011.0111, представляется в виде Ц2)з+ 0(2)г+ Ц2)г + Ц2)о+ 0(2)-~+ Ц2)-з+ Ц2)-з+ Ц2)-4, 1 0 1 1 0 1 1 1 (2) (2)' (2)' (2) (2Г' (2) ~ (2Г~ (2Г' или Следовательно, 530328го = 81798мь Для использования альтернативного метода перевода шестнадцатеричного числа в десятичное необходимо делить на 161о = 10ге вместо деления на 21о = 10з аналогично предыдущему алгоритму перевода десятичного числа в двоичное. Таким образом, имеем следующий алгоритм: 224 ГЛАВА 5.
Алгоритмы и рекурсия Поэтому для преобразования двоичной записи рационального числа в десятичную необходимо каждый разряд числа преобразовать в десятичную систему счисления и результаты сложить. ПРИМЕР 5.37. Преобразовать 1011.1111з в десятичную форму. 1011.1111з = Ц2) + 0(2) + Ц2) + Ц2) + Ц2) + + Ц2)-з + Ц2)-з + «2)-» = 1 1 1 1 = 8+ 0+ 2+ 1+ — + — + — + — = 2 4 8 16 = 11+.5+.25+.125+.0625 = = 11.9375. ПРИМЕР 5.38. Преобразовать 1010.0101з в десятичную форму. 1010.0101з = Ц2) + 0(2) + Ц2) + 0(2) + 0(2) + + 1(2) — 2 + 0(2) — 3 + 1 (2) — 4 1 1 =8+0+2+0+0+ †+О+ = 4 16 = 10 + .25 + .0625 = = 10.3125.
Заметим, что .3729, умноженное на 10, дает 3.729, где первая цифра справа от десятичной точки передвигается на позицию слева от десятичной точки. Если после этого число .729 умножить на 10, то 7 передвинется на позицию слева от десятичной точки. Умножая теперь .29 на 10, мы передвинем 2 в позицию слева от десятичной точки. Наконец, если умножить .9 на 10, то 9 переместится в позицию слева от десятичной точки. Удалив эту цифру, мы получим О. Цифры, последовательно перенесенные слева направо относительно десятичной точки, вновь образуют исходное число .3729.
Таким образом, если для заданного десятичного числа, меньшего единицы, последовательно повторять процесс, состоящий в умножении числа на десять, выборе цифры, стоящей слева от десятичной точки, и последующем ее удалении, до тех пор, пока не останется ни одной цифры, то мы выберем все цифры, входящие в десятичную запись исходного числа. Тот же самый процесс применим и в случае, если задано двоичное число, меньшее единицы. Пусть, например, задано двоичное число .1101.
Умножая его на 10з, т.е. на два, получаем 1.101. Запомнив и удалив 1, мы умножаем .101 на 10, получая 1.01. Вновь запомнив и удалив 1, умножаем .01 на 10, получая 0.1. Наконец, запомнив и удалив О, умножаем .1 на 10; получаем и запоминаем 1. Перемещенные и сохраненные в памяти цифры — это цифры, образующие исходную двоичную запись.
Если десятичное число, меньшее 1, умножить на 2, то слева от десятичной точки должна появляться та же цифра, что и при умножении этого числа в двоичной записи на 10з, и которая является первой цифрой числа в двоичной форме записи. Таким образом, если умножать числа в десятичной системе счисления на 2, запоминать и удалять цифры слева от десятичной точки, то, продолжая этот процесс, мы должны получить цифры, которые образуют РАЗДЕЛ 5.б.
Двоичные и шестнадцатеричные числа 225 число в двоичной записи. Ниже приведены соответствующие операции, преоб- разующие .125 в двоичное число. В них фигурируют одни и те же числа, но в первом столбце они выражены в двоичной, а во втором — в десятичной форме: ПРИМЕР 5.39. Заменить десятичную запись числа .875 двоичной. Сначала умножаем .875 на 2, получаем 1.750.
Удаляем 1, сохраняя 1 как первую цифру двоичного числа. Умножаем .750 на 2, получаем 1.500. Удаляем 1, сохраняя 1 как вторую цифру двоичного числа. Умножаем .500 на 2, получаем 1.000. Удаляем 1, сохраняя 1 как третью цифру двоичного числа. Следовательно, наше число в двоичной форме записи имеет вид .111. В приведенной ниже таблице первый столбец содержит этапы умножения на 2, второй — результаты умножения, а третий — те цифры, которые нужно удалить и запомнить для формирования двоичной записи исходного десятичного числа.
.875 х 2 1.750 1 .750 х 2 1.500 1 .500 х 2 1.000 1 Таким образом, .8751о = .111з. ПРИМЕР 5.40. Десятичную форму записи числа .4 заменить двоичной формой записи. Используя приведенную выше процедуру, получаем .4 х 2 0.8 0 .8 х 2 1.6 1 .6х2 1.2 1 .2 х2 0.4 0 .4 х 2 0.8 0 .8х2 16 1 .6х2 12 1 .2х2 04 0 Заметим, что когда 0.8 повторяется во втором столбце, повторяется и весь процесс, так что представление числа 0.8 в двоичной форме состоит из повторяющихся цифр 0110. Следовательно, .41о = .0110011001100110 = .0110 П Действуя способом, подобным преобразованию двоичного числа в десятичное, замечаем, что 32с.12 в шестнадцатеричной системе счисления записывается в виде 3(16) + 2(16)' + Г(16) + 1(16) 1 + 2(16) двоичная запись Умножим,001 на 10 и получим 0.01.
Удалим О н запомним как 1-ю цифру. Умножнм .01 на 10 н получим 0.1. Удалим О и запомним как 2-ю цифру. Умножим .1 на 10 и получим 1.0. Удалим 1 и запомним как 3-ю цифру. .0012 = .0012. десятичная запись Умножим .125 иа 2 н получим 0.250. Удалим 0 и запомним как 1-ю цифру. Умножим .250 на 2 н получим 0.500. Удалим О и запомним как 2-ю цифру. Умножим .500 на 2 и получим 1.000. Удалим 1 н запомним как 3-ю цифру.
.1251о = .001з. 226 ГЛАВА 5. Алгоритмы и рекурсия что эквивалентно 3(16) + 2(16) + 15(16) + 1(16) + 2(16) или 3 х 256+ 2 х 16+ 15+ — + — = 815+.0625+.0078125 = 1 2 16 256 = 815-0703125го. Поэтому 32Е.12гв = 815.0703125го. Как видим, для чисел, меньших единицы, в шестнадцатеричной системе счисления умножение на 16 — это то же самое, что умножение на 10 в десятичной. Поэтому, по аналогии с переходом от десятичного числа к двоичному, где производилось умножение на 2(= 10з), мы теперь умножаем на 16(= 10ш), запоминаем и удаляем цифру слева от десятичной точки и используем ее как первую цифру.
Далее, умножая на 16, используем цифры слева от десятичной точки как очередные цифры записи числа в шестнадцатеричной форме. Например, рассмотрим число .0703125зо. Умножая на 16, получаем 1,1250000, так что первой цифрой шестнадцатеричной записи будет 1. Умножая далее .125 х 16, получаем 2.0. Поэтому .0703125го = .12ш . .0703125 х 16 1.125 1 .125 х 16 2 О 2 ПРИМЕР 6.41. Требуется заменить десятичную запись числа .875 шестнадцатеричной.
Умножая .875 на 16, получаем 14 = Еш. Поэтому .875го = .Еш. П ПРИМЕР 6.42. Требуется заменить десятичную запись числа .0078125 шестнадцатеричной. Имеем .0078125 х 16 0.125 0 .125 х 16 2.0 2 и .0078125го = 02гв ПРИМЕР 6.43. Преобразуем десятичное число .8 в шестнадцатеричное. Имеем .8х16 128 С .8х16 128 С .8 х 16 12.8 С и, таким образом, .8го = .СССС = .С, Приведенные выше примеры показывают, что периодичность или конечность представления рационального числа является функцией основания соответствующей системы счисления, а не самого рационального числа.
В информатике зачастую важно иметь возможность переходить от шестнадцатеричной формы записи числа к двоичной и обратно. Заметим, что для представления в двоичной форме записи . аыазоаэаватавававазазагао имеем РЯЗДЕЛ 5.6. Двоичные и шестнадцатеричные числа 227 ' аыа1оадаватавававазаза1ао = ° аы2 + аго2 + ад2 ав2 + 11 го д в +ат2 +ав2 +аз2 +а42 + +аз2 +аз2 +а|2 +по = . (аы2 + аш2 + ад2 ав)2 + + (ат2 + ав2 + ав2 + а4)2 + + аз2 + аз2 + аг2 + ао = (аы2 + а1о2 + ад2'ав) 16 + + (ат2 + ав2 + ав2' + а4)16 + + аз2 + аз2 + а12 + ад.
Тогда, если аы2 +аго2 +ад2'+ав, ат2 +ав2 +аваз+ае и аз2 +аз2 +аг2'+ао преобразованы, соответственно, в шестнадцатеричные числа .. Ьз, Дг и 5о, получаем число +Ьз(16)з+6г(16)+до, которое представляет собой шестнадцатеричное число . дзбгйо, Поэтому объединение двоичных цифр в группы по четыре и преобразование их в шестнадцатеричные числа дает преобразование всего числа из двоичной формы в шестнадцатеричную.
Например, рассмотрим двоичное число 1010011001010111. Первые четыре цифры 1010 формируют шестнадцатеричную цифру А, следующие четыре цифры 0110 формируют шестнадцатеричную цифру 6, следующие четыре цифры 0101 дают шестнадцатеричную цифру 5, последние четыре цифры 0111 дают шестнадцатеричную цифру 7.
Поэтому шестнадцатеричное представление рассматриваемого числа А657 имеет вид: 1010 0110 0101 0111 А 6 5 7 Если количество цифр в двоичном представлении не кратно четырем, необходимо впереди дописать нули так, чтобы количество цифр в двоичном представлении стало кратно четырем. Например, пусть дано двоичное число 1010011110. Дописываем впереди 00 и получаем 001010011110, после чего делаем следующее преобразование: 0010 0110 1001 1110 2 6 9 Е Пусть задано двоичное представление рационального числа, такое, например, как 101100.0111101.
Начиная с десятичной точки и двигаясь от нее в каждом направлении, формируем группы по четыре двоичных цифры, дописывая нули в конце каждой группы, если это необходимо. Затем преобразовываем каждую группу из четырех двоичных цифр (двоичных разрядов) в шестнадцатеричную цифру (шестнадцатеричный разряд). Полученное шестнадцатеричное число является представлением исходного числа.
Отсюда имеем: 0010 1100 .0111 1010 2 С .7 А 228 ГЛАВА б. Алгоритмы и рекурсия 0 1 0 1 0 1 1 1О 0 0 0 1 При вычитании важно помнить, что если 1 "занято" из 10, то остается только 1, т.к. 1Оз в действительности есть число 2. ПРИМЕР БА4. Требуется выполнить следующие операции в двоичной системе счисления: а) б) 1100 в) — 1001 011 1011 0110 +0101 10110 1101 х 101 1101 0000 1101 1000001 Аналогично, для шестнадцатеричных чисел правила сложения, вычитания, умножения и деления остаются теми же, за исключением того, что для выполнения сложения и умножения должны быть использованы таблицы, представленные на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
