В прошлой статье мы уже разобрали алгоритм решения самых базовых двух типов 13 заданий. Теперь перед нами стоит задача посложнее — научиться решать задания третьего и четвёртого типов.
Напомним еще раз содержание заданий этих двух типов:
- К третьему типу мы относим задания, в которых известны IP-адреса узла и сети. Обычно в них требуется определить маску такой сети и в ответ дать наименьшее/наибольшее количество нулей или единиц в ней;
- К заданиям четвёртого типа относим те, в которых даны IP-адрес сети и маска подсети. Чаще всего в таких заданиях требуется найти количество IP-адресов, удовлетворяющих какому-либо условию.
Тип 3
Начнём с такой формулировки:
«Для узла с IP-адресом 44.44.229.28 адрес сети равен 44.44.224.0.
Каково наибольшее значение единиц в разрядах маски?»
Давайте продумаем алгоритм решения. Очевидно, что сначала нужно создать объекты обоих адресов.
Затем следует в цикле перебирать возможное количество нулей в маске, строить с такой маской сеть и проверять, входит ли в эту сеть данный узел и является ли адрес сети из условия адресом проверяемой сети.
Если условие выполняется, то вычисляем длину префикса — это и будет количество единиц.
Переходим к коду. Импортируем функции и создаём объекты IP-адреса:
Далее создадим список, в котором будем сохранять все возможные длины префикса:
Теперь организуем перебор значений префикса в цикле. Возникает вопрос: с какого числа начать? Верхняя граница всегда известна — это 32. А нижняя?
Воспользуемся простым правилом: каждый совпадающий у сети и узла октет соответствует 8 единицам в маске. В нашем случае совпадают два октета (44.44.), значит, префикс точно не меньше 16. Начнём перебор с 17:
Запишем это в коде:
Внутри цикла строим сеть с текущим значением префикса. Строим её по адресу узла! Следовательно, не забываем выставить значение strict=False:
Осталось лишь проверить, что адрес узла принадлежит построенной сети, и её адрес совпадает с адресом сети из условия. Если это так, добавляем текущий префикс в список:
В конце выведем максимальное значение из этого списка:
Задание решено, получаем ответ 21.
Пример 1
Рассмотрим еще одно задание:
«Для узла с IP-адресом 244.55.229.28 адрес сети равен 244.0.0.0.
Какое наибольшее возможное количество нулей в разрядах маски?»
Теперь нужно найти количество нулей, а не единиц. Но не стоит отчаиваться, достаточно вспомнить, что в маске всего 32 цифры. Значит, чтобы определить количество нулей, достаточно просто от 32 отнять длину префикса (количество единиц).
В остальном код мало чем отличается. Импортируем функции, создаём объекты и пустой список:
Определим нижнюю границу диапазона. Чем меньше префикс, тем больше узлов в сети и тем дольше будет работать цикл. Ближайшее стандартное значение маски к числу 244 — это 240.0.0.0, что соответствует длине префикса 4. С этого числа и начнём:
Далее все шаблонно: строим сеть, проверяем узел и адрес сети. Но в список добавляем не длину префикса, а количество нулей (32 — prefixlen):
Таким образом, в списке prefixlen мы собираем количество нулей в маске. Осталось лишь вывести максимальное число из этого списка:
Запустим программу, подождём и получим число 26. Но такой код порой может выполняться очень долго. И тут приходит на помощь ручное решение.
Вспомним, что адрес сети получается применением побитовой конъюнкции маски к адресу узла. Там, где в маске стоит единица, бит адреса узла сохраняется; там, где ноль, — заменяется на ноль.
Чтобы получить адрес сети 244.0.0.0 из адреса узла 244.55.229.28, нужно подобрать маску с максимальным числом нулей, при которой результат операции даёт указанный адрес сети.
Переведём первый октет в двоичный вид: 244 = 11110100. Адрес сети начинается так же. Чтобы после конъюнкции этот октет остался равен 244, достаточно сохранить только старшие биты до последней единицы: 111101. Два последних нуля в любом случае дадут ноль при конъюнкции.
Во всех остальных разрядах маски можно поставить нули. Получаем маску:
Получаем маску 11111100 00000000 00000000 00000000, в которой 26 нулей.
Проверим наше решение:
Здесь оранжевые цифры всегда должны оставаться как в адресе узла, так и в адресе сети. Чтобы они остались, на этих же позициях (1-6) в маске должны стоять единицы, всё остальное можно заполнить нулями.
Пример 2
Закрепим ручное решение с помощью разбора следующего задания:
«Для узла с IP-адресом 192.168.24.72 адрес сети равен 192.168.24.64.
Определите наименьшее возможное количество единиц в последних двух байтах маски.»
Первым делом нам нужно перевести все IP-адреса в двоичный вид. Начнём с адреса узла: 192.168.24.72. Переводим каждое число:
- 192 → 11000000
- 168 → 10101000
- 24 → 00011000
- 72 → 01001000
Собираем всё вместе: 11000000 10101000 00011000 01001000
Аналогично получаем адрес сети в двоичном представлении: 11000000 10101000 00011000 01000000. Напишем их друг под другом, оставив пустую строку под маску.
Посмотрите внимательно на оба адреса. Первые три октета у них полностью совпадают. Различие начинается только в последнем октете: у узла там 01001000 (72), а у сети — 01000000 (64).
Еще раз вспоминаем, как работает маска при побитовой конъюнкции:
- Там, где в маске стоит единица, бит из адреса узла сохраняется
- Там, где в маске стоит ноль, бит результата становится нулём
Нам нужно, чтобы после применения маски к адресу узла получился адрес сети. Значит:
- На тех позициях, где биты адреса узла и адреса сети совпадают, в маске может стоять единица
- На тех позициях, где в адресе узла единица, а в адресе сети ноль, в маске обязательно должен стоять ноль (чтобы «погасить» эту единицу)
Поскольку нам нужно минимальное количество единиц, мы будем ставить единицы только там, где это точно необходимо.
Единицы в маске обязательно нужны слева — они определяют сетевую часть адреса. Мы должны поставить единицы как минимум до того места, где в адресе сети заканчиваются значащие биты (то есть до последней единицы в адресе сети).
Смотрим на адрес сети: 11000000 10101000 00011000 01000000
Последняя единица в адресе сети находится на второй позиции последнего октета (выделена оранжевым). Значит, маска должна содержать единицы как минимум до этой позиции включительно.
Смело заполняем маску единицами слева направо до этой позиции:
Проверим, можно ли добавить ещё единицы:
- 3-й бит: узел — 0, сеть — 0 → можно поставить единицу
- 4-й бит: узел — 0, сеть — 0 → можно поставить единицу
- 5-й бит: узел — 1, сеть — 0 → нельзя ставить единицу!
Если поставить единицу на 5-й позиции, при конъюнкции получится не адрес сети, а адрес узла.
А поскольку нам нужно наименьшее количество единиц, то добавлять единицы на 3 и 4 биты мы не будем! Остановимся на минимальной маске:
11111111 11111111 11111111 11000000.
Считаем единицы в последних двух байтах и получаем число 10 — это и будет ответом на данное задание.
Тип 4
Переходим к следующему типу. Здесь нам может встретиться задание с такой формулировкой:
«Сеть задана IP-адресом 204.16.168.0 и сетевой маской 255.255.248.0.
Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса не кратно 5?»
В заданиях данного типа есть сразу несколько подходов, которые могут значительно ускорить работу вашего кода. Сначала решим самым простым методом, а затем рассмотрим некоторые улучшения.
Базовый код здесь несложный. Импортируем функцию, создаём сеть, заводим переменную под счетчик подходящих IP-адресов:
Теперь перебираем все объекты IP-адресов внутри объекта net:
Из каждого адреса формируем строку из 32 двоичных символов:
Считаем в этой строке количество единиц, если оно не кратно 5, то увеличиваем счётчик:
В конце выводим значение cnt:
Получим число 1663.
Но на каждой итерации цикла перегонять объект IP-адреса в бинарную строку и подсчитывать символы «1» в ней не очень эффективно.
Поскольку нам нужно считать именно количество бит в адресе, то здесь эффективнее использовать специальную функцию — bit_count() — она работает на уровне битов и выполняется значительно быстрее обычного count().
Тогда нам достаточно получить из объекта IP-адреса целое число и подсчитать в нём количество бит (единиц в двоичной записи). Выглядеть наш код будет так:
Можно пойти ещё дальше и перебирать числа напрямую, без создания объектов IPv4Address:
Пример 1
Рассмотрим еще одно задание этого типа:
«Сеть задана IP-адресом 252.67.33.87 и сетевой маской 255.252.0.0.
Сколько в этой сети IP-адресов, для которых в двоичной записи IP-адреса суммарное количество единиц в правых двух байтах более чем вдвое превосходит суммарное количество единиц в левых двух байтах?»
И снова сначала приведём самое простое решение «в лоб», а затем разберём некоторые оптимизации.
Начало будет идентичным прошлому примеру, только теперь нужно добавить аргумент strict=False:
Теперь разобьём строку ip на две части по 16 символов:
И проверим, что справа в ней более, чем в 2 раза больше единиц, чем слева:
Если условие вернёт истину, увеличится счётчик cnt. В конце выведем его значение:
В результате получаем ответ 17.
Но улучшения здесь будут немного сложнее, чем в прошлом случае. Здесь понадобятся знания побитовых сдвигов. Чтобы отбросить младшие16 бит и получить только «левую» часть адреса можно воспользоваться такой записью:
Получить же «правую» часть можно побитовой конъюнкцией. В Python для этого служит оператор «&».
Число 0xFFFF в бинарном виде это: 11111111 11111111. То есть мы такой маской оставляем только первые 16 цифр IP-адреса.
Используем это в коде:
Здесь в переменных left и right сразу подсчитано количество единиц с помощью уже знакомой нам функции bit_count().
Дополнительно можно сократить количество проверяемых адресов, если проанализировать, какие биты вообще могут меняться при такой маске и какие из них могут влиять на ответ. Но обычно хватает и шаблонного решения, приведённого в самом начале.
Пример 2
Закрепим решение с помощью шаблонного кода и побитовых операций на таком задании:
«Сеть задана IP-адресом 142.108.56.118 и сетевой маской 255.255.255.240.
Сколько в этой сети IP-адресов, для которых в двоичной записи IP-адреса суммарное количество единиц в левых двух байтах меньше суммарного количества единиц в правых двух байтах?»
Оно очень похоже на предыдущее, разве что условие в цикле будет немного отличаться. В остальном же трудностей возникнуть не должно, так что шаблонному решению уделим меньше внимания и сконцентрируемся на коде с побитовыми операциями.
И перейдём к решению с помощью побитовых операций. Начало не меняем:
В цикле будем перебирать все IP-адреса полученной сети и сразу приводить каждый адрес к целочисленному типу:
Далее для получения двух левых мы «отбрасываем» 16 бит справа с помощью побитового сдвига: x >> 16. И в этой же строке подсчитываем количество единиц в двоичной записи получившегося число с помощь bit_count():
Затем получим правые два байта. Применим побитовую конъюнкцию переменной x с числом 0xFFFF. Тем самым «обнулив» все биты, кроме последних шестнадцати, то есть оставляем только правые два байта. После этого bit_count() подсчитает количество единиц.
Осталось лишь сравнить количество единиц справа и слева. Если слева единиц меньше — увеличиваем счётчик на единицу:
В конце выводим значение переменной-счётчика cnt на экран:
Запускаем программу и получаем ответ — число 5.
Мы разобрали еще два типа 13 заданий: третий, где по известным адресам узла и сети нужно определить характеристики маски, и четвёртый, где требуется подсчитать IP-адреса с определёнными свойствами.
Для третьего типа полезно владеть как программным перебором, так и ручным анализом двоичных записей — это может существенно сэкономить время на экзамене.
Для четвёртого типа базовое решение с преобразованием в строку работает всегда, но использование bit_count() и побитовых операций значительно ускоряет выполнение кода.
В следующей статье мы разберём оставшиеся три типа заданий — те, в которых один из байтов IP-адреса или маски неизвестен и обозначен буквой А. Эти задания требуют немного другого подхода, но с полученной базой вы легко с ними справитесь.