В прошлой статье мы уже разобрали алгоритм решения самых базовых двух типов 13 заданий. Теперь перед нами стоит задача посложнее — научиться решать задания третьего и четвёртого типов.
Напомним еще раз содержание заданий этих двух типов:
- К третьему типу мы относим задания, в которых известны IP-адреса узла и сети. Обычно в них требуется определить маску такой сети и в ответ дать наименьшее/наибольшее количество нулей или единиц в ней;
- К заданиям четвёртого типа относим те, в которых даны IP-адрес сети и маска подсети. Чаще всего в таких заданиях требуется найти количество IP-адресов, удовлетворяющих какому-либо условию.
Навигация по странице
Тип 3
Начнём с такой формулировки:
Задание 1311
«Для узла с IP-адресом 44.44.229.28 адрес сети равен 44.44.224.0.
Каково наибольшее значение единиц в разрядах маски?»
Давайте продумаем алгоритм решения. Очевидно, что сначала нужно создать объекты обоих адресов.
Затем следует в цикле перебирать возможное количество нулей в маске, строить с такой маской сеть и проверять, входит ли в эту сеть данный узел и является ли адрес сети из условия адресом проверяемой сети.
Если условие выполняется, то вычисляем длину префикса — это и будет количество единиц.
Переходим к коду. Импортируем функции и создаём объекты IP-адреса:
from ipaddress import ip_network, ip_address
ip_net = ip_address('44.44.224.0')
ip_host = ip_address('44.44.229.28')
Далее создадим список, в который будем помещать все возможные длины префикса:
from ipaddress import ip_network, ip_address
ip_net = ip_address('44.44.224.0')
ip_host = ip_address('44.44.229.28')
prefixlen = []
Теперь организуем перебор значений префикса в цикле. Возникает вопрос: с какого числа начать? Верхняя граница всегда известна — это 32. А нижняя?
Воспользуемся простым правилом: каждый совпадающий у сети и узла октет соответствует 8 единицам в маске. В нашем случае совпадают два октета (44.44.), значит, префикс точно не меньше 16. Начнём перебор с 17:
Запишем это в коде:
from ipaddress import ip_network, ip_address
ip_net = ip_address('44.44.224.0')
ip_host = ip_address('44.44.229.28')
prefixlen = []
for mask in range(17, 32):
Внутри цикла строим сеть с текущим значением префикса. Строим её по адресу узла! Следовательно, не забываем выставить значение strict=False:
from ipaddress import ip_network, ip_address
ip_net = ip_address('44.44.224.0')
ip_host = ip_address('44.44.229.28')
prefixlen = []
for mask in range(17, 32):
net = ip_network(f'{ip_host}/{mask}', strict=False)
Осталось лишь проверить, что адрес узла принадлежит построенной сети, и её адрес совпадает с адресом сети из условия. Если это так, добавляем текущий префикс в список:
from ipaddress import ip_network, ip_address
ip_net = ip_address('44.44.224.0')
ip_host = ip_address('44.44.229.28')
prefixlen = []
for mask in range(17, 32):
net = ip_network(f'{ip_host}/{mask}', strict=False)
if ip_host in net.hosts() and net.network_address == ip_net:
prefixlen.append(net.prefixlen)
В конце выведем максимальное значение из этого списка:
from ipaddress import ip_network, ip_address
ip_net = ip_address('44.44.224.0')
ip_host = ip_address('44.44.229.28')
prefixlen = []
for mask in range(17, 32):
net = ip_network(f'{ip_host}/{mask}', strict=False)
if ip_host in net.hosts() and net.network_address == ip_net:
prefixlen.append(net.prefixlen)
print(max(prefixlen))
Задание решено, получаем ответ 21.
Пример 1
Рассмотрим еще одно задание:
Задание 1325
«Для узла с IP-адресом 244.55.229.28 адрес сети равен 244.0.0.0.
Какое наибольшее возможное количество нулей в разрядах маски?»
Теперь нужно найти количество нулей, а не единиц. Но не стоит отчаиваться, достаточно вспомнить, что в маске всего 32 цифры. Значит, чтобы определить количество нулей, достаточно просто от 32 отнять длину префикса (количество единиц).
В остальном код мало чем отличается. Импортируем функции, создаём объекты и пустой список:
from ipaddress import ip_network, ip_address
ip_net = ip_address('244.0.0.0')
ip_host = ip_address('244.55.229.28')
prefixlen = []
Определим нижнюю границу диапазона. Чем меньше префикс, тем больше узлов в сети и тем дольше будет работать цикл. Ближайшее стандартное значение маски к числу 244 — это 240.0.0.0, что соответствует длине префикса 4. С этого числа и начнём:
from ipaddress import ip_network, ip_address
ip_net = ip_address('244.0.0.0')
ip_host = ip_address('244.55.229.28')
prefixlen = []
for mask in range(4, 32):
Далее все шаблонно: строим сеть, проверяем узел и адрес сети. Но в список добавляем не длину префикса, а количество нулей (32 — prefixlen):
from ipaddress import ip_network, ip_address
ip_net = ip_address('244.0.0.0')
ip_host = ip_address('244.55.229.28')
prefixlen = []
for mask in range(4, 32):
net = ip_network(f'{ip_host}/{mask}', strict=False)
if ip_host in net.hosts() and net.network_address == ip_net:
prefixlen.append(32 - net.prefixlen)
Таким образом, в списке prefixlen мы собираем количество нулей в маске. Осталось лишь вывести максимальное число из этого списка:
from ipaddress import ip_network, ip_address
ip_net = ip_address('244.0.0.0')
ip_host = ip_address('244.55.229.28')
prefixlen = []
for mask in range(4, 32):
net = ip_network(f'{ip_host}/{mask}', strict=False)
if ip_host in net.hosts() and net.network_address == ip_net:
prefixlen.append(32 - net.prefixlen)
print(max(prefixlen))
Запустим программу, подождём и получим число 26. Но такой код порой может выполняться очень долго. И тут приходит на помощь ручное решение.
Вспомним, что адрес сети получается применением побитовой конъюнкции маски к адресу узла. Там, где в маске стоит единица, бит адреса узла сохраняется; там, где ноль, — заменяется на ноль.
Чтобы получить адрес сети 244.0.0.0 из адреса узла 244.55.229.28, нужно подобрать маску с максимальным числом нулей, при которой результат операции даёт указанный адрес сети.
Переведём первый октет в двоичный вид: 244 = 11110100. Адрес сети начинается так же. Чтобы после конъюнкции этот октет остался равен 244, достаточно сохранить только старшие биты до последней единицы: 111101. Два последних нуля в любом случае дадут ноль при конъюнкции.
Во всех остальных разрядах маски можно поставить нули. Получаем маску:
Получаем маску 11111100 00000000 00000000 00000000, в которой 26 нулей.
Проверим наше решение:
Здесь оранжевые цифры всегда должны оставаться как в адресе узла, так и в адресе сети. Чтобы они остались, на этих же позициях (1-6) в маске должны стоять единицы, всё остальное можно заполнить нулями.
Пример 2
Закрепим ручное решение с помощью разбора следующего задания:
Задание 1307
«Для узла с 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
Переходим к следующему типу. Здесь нам может встретиться задание с такой формулировкой:
Задание 1309
«Сеть задана IP-адресом 204.16.168.0 и сетевой маской 255.255.248.0.
Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса не кратно 5?»
В заданиях данного типа есть сразу несколько подходов, которые могут значительно ускорить работу вашего кода. Сначала решим самым простым методом, а затем рассмотрим некоторые улучшения.
Базовый код здесь несложный. Импортируем функцию, создаём сеть, заводим переменную под счетчик подходящих IP-адресов:
from ipaddress import ip_network
net = ip_network('204.16.168.0/255.255.248.0')
cnt = 0
Теперь перебираем все объекты IP-адресов внутри объекта net:
from ipaddress import ip_network
net = ip_network('204.16.168.0/255.255.248.0')
cnt = 0
for i in net:
Из каждого адреса формируем строку из 32 двоичных символов:
from ipaddress import ip_network
net = ip_network('204.16.168.0/255.255.248.0')
cnt = 0
for i in net:
ip = f'{int(i):032b}'
Считаем в этой строке количество единиц, если оно не кратно 5, то увеличиваем счётчик:
from ipaddress import ip_network
net = ip_network('204.16.168.0/255.255.248.0')
cnt = 0
for i in net:
ip = f'{int(i):032b}'
if ip.count('1') % 5:
cnt += 1
В конце выводим значение cnt:
from ipaddress import ip_network
net = ip_network('204.16.168.0/255.255.248.0')
cnt = 0
for i in net:
ip = f'{int(i):032b}'
if ip.count('1') % 5:
cnt += 1
print(cnt)
Получим число 1663.
Но на каждой итерации цикла перегонять объект IP-адреса в бинарную строку и подсчитывать символы «1» в ней не очень эффективно.
Поскольку нам нужно считать именно количество бит в адресе, то здесь эффективнее использовать специальную функцию — bit_count() — она работает на уровне битов и выполняется значительно быстрее обычного count().
Тогда нам достаточно получить из объекта IP-адреса целое число и подсчитать в нём количество бит (единиц в двоичной записи). Выглядеть наш код будет так:
from ipaddress import ip_network
net = ip_network('204.16.168.0/255.255.248.0')
cnt = 0
for ip in net:
if int(ip).bit_count() % 5:
cnt += 1
print(cnt)
Можно пойти ещё дальше и перебирать числа напрямую, без создания объектов IPv4Address:
from ipaddress import ip_network
net = ip_network('204.16.168.0/255.255.248.0')
start = int(net.network_address)
end = int(net.broadcast_address)
cnt = 0
for ip in range(start, end + 1):
if ip.bit_count() % 5:
cnt += 1
print(cnt)
Пример 1
Рассмотрим еще одно задание этого типа:
Задание 1323
«Сеть задана IP-адресом 252.67.33.87 и сетевой маской 255.252.0.0.
Сколько в этой сети IP-адресов, для которых в двоичной записи IP-адреса суммарное количество единиц в правых двух байтах более чем вдвое превосходит суммарное количество единиц в левых двух байтах?»
И снова сначала приведём самое простое решение «в лоб», а затем разберём некоторые оптимизации.
Начало будет идентичным прошлому примеру, только теперь нужно добавить аргумент strict=False:
from ipaddress import ip_network
net = ip_network('252.67.33.87/255.252.0.0', strict=False)
cnt = 0
for i in net:
ip = f'{int(i):032b}'
Теперь разобьём строку ip на две части по 16 символов:
from ipaddress import ip_network
net = ip_network('252.67.33.87/255.252.0.0', strict=False)
cnt = 0
for i in net:
ip = f'{int(i):032b}'
two_left = ip[:16]
two_right = ip[16:]
И проверим, что справа в ней более, чем в 2 раза больше единиц, чем слева:
from ipaddress import ip_network
net = ip_network('252.67.33.87/255.252.0.0', strict=False)
cnt = 0
for i in net:
ip = f'{int(i):032b}'
two_left = ip[:16]
two_right = ip[16:]
if two_right.count('1') / two_left.count('1') > 2:
Если условие вернёт истину, увеличится счётчик cnt. В конце выведем его значение:
from ipaddress import ip_network
net = ip_network('252.67.33.87/255.252.0.0', strict=False)
cnt = 0
for i in net:
ip = f'{int(i):032b}'
two_left = ip[:16]
two_right = ip[16:]
if two_right.count('1') / two_left.count('1') > 2:
cnt += 1
print(cnt)
В результате получаем ответ 17.
Но улучшения здесь будут немного сложнее, чем в прошлом случае. Здесь понадобятся знания побитовых сдвигов. Чтобы отбросить младшие16 бит и получить только «левую» часть адреса можно воспользоваться такой записью:
left = ip >> 16
Получить же «правую» часть можно побитовой конъюнкцией. В Python для этого служит оператор «&».
right = ip & 0xFFFF
Число 0xFFFF в бинарном виде это: 11111111 11111111. То есть мы такой маской оставляем только первые 16 цифр IP-адреса.
Используем это в коде:
from ipaddress import ip_network
net = ip_network('252.67.33.87/255.252.0.0', False)
cnt = 0
for ip in net:
x = int(ip)
left = (x >> 16).bit_count()
right = (x & 0xFFFF).bit_count()
if right > 2 * left:
cnt += 1
print(cnt)
Здесь в переменных left и right сразу подсчитано количество единиц с помощью уже знакомой нам функции bit_count().
Дополнительно можно сократить количество проверяемых адресов, если проанализировать, какие биты вообще могут меняться при такой маске и какие из них могут влиять на ответ. Но обычно хватает и шаблонного решения, приведённого в самом начале.
Пример 2
Закрепим решение с помощью шаблонного кода и побитовых операций на таком задании:
Задание 1310
«Сеть задана IP-адресом 142.108.56.118 и сетевой маской 255.255.255.240.
Сколько в этой сети IP-адресов, для которых в двоичной записи IP-адреса суммарное количество единиц в левых двух байтах меньше суммарного количества единиц в правых двух байтах?»
Оно очень похоже на предыдущее, разве что условие в цикле будет немного отличаться. В остальном же трудностей возникнуть не должно, так что шаблонному решению уделим меньше внимания и сконцентрируемся на коде с побитовыми операциями.
from ipaddress import ip_network
net = ip_network('142.108.56.118/255.255.255.240', strict=False)
cnt = 0
for i in net:
ip = f'{int(i):032b}'
two_left = ip[:16]
two_right = ip[16:]
if two_left.count('1') < two_right.count('1'):
cnt += 1
print(cnt)
И перейдём к решению с помощью побитовых операций. Начало не меняем:
from ipaddress import ip_network
net = ip_network('142.108.56.118/255.255.255.240', strict=False)
cnt = 0
В цикле будем перебирать все IP-адреса полученной сети и сразу приводить каждый адрес к целочисленному типу:
from ipaddress import ip_network
net = ip_network('142.108.56.118/255.255.255.240', strict=False)
cnt = 0
for ip in net:
x = int(ip)
Далее для получения двух левых мы «отбрасываем» 16 бит справа с помощью побитового сдвига: x >> 16. И в этой же строке подсчитываем количество единиц в двоичной записи получившегося число с помощь bit_count():
from ipaddress import ip_network
net = ip_network('142.108.56.118/255.255.255.240', strict=False)
cnt = 0
for ip in net:
x = int(ip)
two_left = (x >> 16).bit_count()
Затем получим правые два байта. Применим побитовую конъюнкцию переменной x с числом 0xFFFF. Тем самым «обнулив» все биты, кроме последних шестнадцати, то есть оставляем только правые два байта. После этого bit_count() подсчитает количество единиц.
from ipaddress import ip_network
net = ip_network('142.108.56.118/255.255.255.240', strict=False)
cnt = 0
for ip in net:
x = int(ip)
two_left = (x >> 16).bit_count()
two_right = (x & 0xFFFF).bit_count()
Осталось лишь сравнить количество единиц справа и слева. Если слева единиц меньше — увеличиваем счётчик на единицу:
from ipaddress import ip_network
net = ip_network('142.108.56.118/255.255.255.240', strict=False)
cnt = 0
for ip in net:
x = int(ip)
two_left = (x >> 16).bit_count()
two_right = (x & 0xFFFF).bit_count()
if two_left< two_right:
cnt += 1
В конце выводим значение переменной-счётчика cnt на экран:
from ipaddress import ip_network
net = ip_network('142.108.56.118/255.255.255.240', strict=False)
cnt = 0
for ip in net:
x = int(ip)
two_left = (x >> 16).bit_count()
two_right = (x & 0xFFFF).bit_count()
if two_left< two_right:
cnt += 1
print(cnt)
Запускаем программу и получаем ответ — число 5.
Мы разобрали еще два типа 13 заданий: третий, где по известным адресам узла и сети нужно определить характеристики маски, и четвёртый, где требуется подсчитать IP-адреса с определёнными свойствами.
Для третьего типа полезно владеть как программным перебором, так и ручным анализом двоичных записей — это может существенно сэкономить время на экзамене.
Для четвёртого типа базовое решение с преобразованием в строку работает всегда, но использование bit_count() и побитовых операций значительно ускоряет выполнение кода.
В следующей статье мы разберём оставшиеся три типа заданий — те, в которых один из байтов IP-адреса или маски неизвестен и обозначен буквой А. Эти задания требуют немного другого подхода, но с полученной базой вы легко с ними справитесь.