Мы уже рассмотрели три действия и думаю уже понятно, что в общем-то действия над двоичными числами мало отличаются от действий над десятичными числами. Разница появляется только в том, что цифр две а не десять, но это только упрощает арифметические операции. Так же обстоит дело и с делением, но для лучшего понимания алгоритм деления разберём более подробно. Пусть нам необходимо разделить два десятичных числа, например 234 разделить на 7. Как мы это делаем.
Выделяем справа (от старшего разряда) такое количество цифр, чтобы получившееся число было как можно меньше и в то же время больше делителя. 2 — меньше делителя, следовательно, необходимое нам число 23. Затем делим полученное число на делитель с остатком. Получаем следующий результат:
| — | |||||
Описанную операцию повторяем до тех пор, пока полученный остаток не окажется меньше делителя. Когда это случится, число полученное под чертой будет частным, а последний остаток – остатком от деления. Операция деления двоичного числа выполняется точно также. Рассмотрим пример.
Пример: Вычислить 10010111 / 101.
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | ||||
Начиная со старшего разряда, ищем число, которое первое было бы больше чем делитель. Это четырехразрядное число 1001. Оно выделено жирным шрифтом. Теперь необходимо подобрать делитель выделенному числу. И здесь мы опять выигрываем в сравнении с десятичной системой. Дело в том, что подбираемый делитель это обязательно цифра, а цифры у нас только две. Так как 1001 явно больше 101, то с делителем всё понятно это 1. Выполним шаг операции.
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | |||||
| — | |||||||||||
Итак, остаток от выполненной операции 100. Это меньше чем 101, поэтому чтобы выполнить второй шаг деления, необходимо добавить к 100 следующую цифру, это цифра 0. Теперь имеем следующее число:
| — | |||||||||||
1000 больше 101 поэтому на втором шаге мы опять допишем в частное цифру 1 и получим следующий результат (для экономии места сразу опустим следующую цифру).
| — | |||||||||||
| — | |||||||||||
Третий шаг. Полученное число 110 больше 101, поэтому и на этом шаге мы запишем в частное 1. Получиться так:
| — | |||||||||||
| — | |||||||||||
| — | |||||||||||
Полученное число 11 меньше 101 поэтому записываем в частное цифру 0 и опускаем вниз следующую цифру. Получается:
| — | ||||||||||||||
| — | ||||||||||||||
| — | ||||||||||||||
Полученное число больше 101, поэтому в частное записываем цифру 1 и опять выполняем действия. Получается:
| — | ||||||||||||||
| — | ||||||||||||||
| — | ||||||||||||||
| — | ||||||||||||||
Полученный остаток 10 меньше 101, но у нас закончились цифры в делимом, поэтому 10 это окончательный остаток, а 1110 это искомое частное.
Сделаем проверку в десятичных числах:
10010011 = 147
101 = 5
10 = 2
11101 = 29
| — | |||||
| — | |||||
На этом мы заканчиваем описание простейших арифметических операций, которые необходимо знать, для того, чтобы пользоваться двоичной арифметикой, и теперь попробуем ответить на вопрос Зачем нужна двоичная арифметика. Конечно, выше уже было показано, что запись числа в двоичной системе существенно упрощает арифметические операции, но в то же время сама запись становится значительно длиннее, что уменьшает ценность полученного упрощения, поэтому необходимо поискать такие задачи, решение которых существенно проще в двоичных числах.
Задача 1: Получение всех выборок
Очень часто встречаются задачи, в которых нужно уметь построить все возможные комбинации из заданного набора предметов. Например, такая задача:
Дана большая куча камней, разложить камни по двум кучам таким образом, чтобы масса этих двух куч была как можно более близкой.
Эту задачу можно сформулировать так:
Найти такую выборку камней из большой кучи, что её общая масса будет как можно менее отличаться от половины массы большой кучи.
Задач такого сорта довольно много. И все они сводятся, как уже было сказано, к умению получить все возможные комбинации (далее мы будем называть их выборками) из заданного набора элементов. И сейчас мы рассмотрим общий метод получения всех возможных выборок с использованием операции сложения двоичных чисел. А начнём с примера. Пусть есть множество из трёх предметов. Построим все возможные выборки. Предметы будем обозначать порядковыми номерами. То есть, имеются следующие предметы: 1, 2, 3.
Выборки: (0, 0, 1); (0, 1, 0); (0, 1, 1); (1, 0, 0); (1, 0, 1); (1, 1, 0); (1, 1, 1);
Если в позиции с очередным номером стоит единица, то это означает, что элемент с номером равным этой позиции присутствует в выборке, а если стоит ноль, то элемент не присутствует. Например, выборка (0, 1, 0); состоит из одного элемента с номером 2, а выборка (1, 1, 0); состоит из двух элементов с номерами 1 и 2.
Из этого примера ясно видно, что выборку можно представить в виде двоичного числа. Кроме того, нетрудно заметить, что выше записаны все возможные одно, двух и трехзначные двоичные числа. Перепишем их следующим образом:
001; 010; 011; 100; 101; 110; 111
Будем считать младшим разрядом первый справа, отбросим незначащие нули (то есть нули в старших разрядах до первой единицы), и получим следующий ряд:
1; 10; 11; 100; 101; 110; 111
Мы получили ряд последовательных двоичных чисел, каждое из которых получается из предыдущего прибавлением единицы. Можете это проверить. Используя эту замеченную закономерность можно построить следующий алгоритм получения выборок.
Исходные данные алгоритма
Дан набор предметов N — штук. Далее будем называть этот набор множеством исходных элементов. Пронумеруем все элементы исходного множества от 1 до N. Составим двоичное число из N незначащих нулей. 0000… 0N Это нулевое двоичное число будет обозначать нулевую выборку с которой и начнётся процесс составления выборок. Разряды числа считаются справа налево, то есть самый левый разряд это самый старший.
Договоримся обозначать это двоичное число большими буквами ДВОИЧНОЕ
Алгоритм
Если ДВОИЧНОЕ число состоит целиком из единиц
То прекращаем работу алгоритма
Иначе
Начало
§ Прибавляем к ДВОИЧНОМУ числу единицу по правилам двоичной арифметики.
§ Из полученного ДВОИЧНОГО числа составляем очередную выборку, как было описано выше.
Конец
Задача 2: Поиск больших простых чисел
Для начала вспомним, что простым числом называется такое натуральное число, которое делится только на 1 и на само себя. Примеры простых чисел: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.
Поиск больших простых чисел — очень важная математическая задача. Большие простые числа необходимы для надёжного шифрования сообщений некоторыми алгоритмами шифрования. Причём необходимы не просто большие числа, а очень большие. Чем число больше, тем надежнее шифр, построенный на этом числе.
Примечание. Надёжным шифром называется такой шифр, для расшифровки которого нужно очень большое время.
Почему? Простое число играет роль ключа при шифровке и дешифровке. Кроме того, мы знаем, что простые числа встречаются в ряду натуральных чисел не слишком часто. Их достаточно много среди первой тысячи, потом их количество начинает быстро убывать. Поэтому если в качестве ключа мы возьмём не очень большое число, дешифровальщик с помощью даже не очень быстрого компьютера сможет до него добраться (перебирая в качестве ключа все простые одно за другим) за ограниченное время.
Достаточно надежный код можно получить если взять простое в котором, например 150 знаков. Однако, найти такое простое не так просто. Предположим, что некоторое число А (очень большое) нужно проверить на простоту. Это тоже самое, что поискать его делители. Если мы сможем найти делители в интервале от 2 до корень квадратный из А, то оно не простое. Оценим количество чисел которые необходимо проверить на способность разделить число А.
Предположим число А имеет 150 знаков. Корень квадратный из него будет содержать не менее 75 знаков. Чтобы перебрать такое количество возможных делителей нам потребуется очень мощный компьютер и огромное время, а это означает, что задача практически не решаема.
Как с этим бороться
Во-первых, можно поучится быстрее осуществлять проверку на делимость одного числа на другое, во-вторых можно попытаться число А подбирать таким образом, чтобы оно было простым с высокой степенью вероятности. Оказывается это возможно. Математик Мерсен обнаружил, что числа следующего вида
2n — 1
Являются простыми с высокой степенью вероятности.
Чтобы понять написанную выше фразу, посчитаем, сколько простых чисел находится в первой тысяче, и сколько чисел Мерсена в этой же тысяче являются простыми. Итак, числа Мерсена в первой тысяче — это следующие:
21 — 1 = 1; 22 -1 = 3; 23 — 1 = 7; 24 — 1 = 15; 25 — 1 = 31; 26 -1 = 63;
27 — 1 =127; 28 -1 = 255; 29 — 1 = 511;
Жирным шрифтом помечены простые числа. Всего на 9 чисел Мерсена 5 простых. В процентах это 5/9*100 = 55,6%. В то же время на 1000 первых натуральных чисел только 169 простых. В процентах это 169/1000*100 = 16,9%. То есть в первой тысяче в процентом отношении простые среди чисел Мерсена встречаются почти в 4 раза чаще, чем среди просто натуральных чисел
А теперь возьмём конкретное число Мерсена, например 24 — 1. Запишем его в виде двоичного числа.
24 — 1 = 10000 — 1 = 1111
Возьмём следующее число Мерсена 25 -1 и запишем его двоичным числом. Получим следующее:
25 -1 = 100000 — 1 = 11111
Уже видно, что все числа Мерсена представляют собой последовательность единиц, и уже сам этот факт даёт большой выигрыш. Во-первых, в двоичной системе счисления очень просто получить очередное число Мерсена. Для этого достаточно к очередному числу дописать единицу. Во-вторых, искать делители в двоичной системе на много проще, чем в десятичной.