Статья Автор: Деникина Н.В., Деникин А.В.

Адреса с нужным числом единиц

Считаем не все адреса, а избранные

В прошлой тетради считали адреса подряд: нулей n — адресов 2ⁿ. Теперь в счёт идут не все, а только те, где единиц в двоичной записи ровно столько, сколько сказано.

И задача перевёрнута: число таких адресов дано, найти надо маску. Масок всего 32, перебрать несложно — вопрос в том, как быстро посчитать адреса для одной из них.

Считаем адреса при одной маске

Маска режет адрес на две части, и части ведут себя по-разному.

Слева адрес сети. Он одинаков у всех адресов подсети, и единицы в нём посчитаны раз и навсегда — обозначим их количество за b.

Справа свободные биты, их n. Каждый адрес подсети — это своя расстановка нулей и единиц по этим n местам.

Чтобы во всём адресе вышло ровно 18 единиц, в свободной части их должно быть 18 − b. А расставить 18 − b единиц по n местам можно C(n, 18 − b) способами — это и есть количество нужных адресов.

Пример

Узел с IP-адресом 196.138.142.89 принадлежит подсети, в которой 78 адресов с 18 единицами в двоичной записи. Сколько единиц в маске?

Шаг 1. Проверить одну маску целиком

Возьмём маску из 19 единиц, то есть 255.255.224.0. Ломается третий байт: 142 и 224 дают 128, поэтому адрес сети 196.138.128.0.

Единиц в нём: 196 даёт 3, 138 даёт 3, 128 даёт 1. Итого b = 7. Свободных бит n = 32 − 19 = 13.

В хвосте надо набрать 18 − 7 = 11 единиц из 13 мест: C(13, 11) = 78. Ровно то число, что в условии.

Шаг 2. Прогнать соседние маски

Та же арифметика, только маска другая.

маска	адрес сети	b	n	нужно в хвосте	адресов
/16	196.138.0.0	6	16	12	1820
/17	196.138.128.0	7	15	11	1365
/18	196.138.128.0	7	14	11	364
/19	196.138.128.0	7	13	11	78
/20	196.138.128.0	7	12	11	12
/21	196.138.136.0	8	11	10	11

У масок с /17 по /20 адрес сети один и тот же, меняется только число свободных мест — и счётчик рушится в разы. Совпадение единственное.

Шаг 3. Ответ

В маске 19 единиц. Спросили бы нули — 32 − 19 = 13.

Программа: та же формула

Строка в строку повторяет разбор: адрес сети, b, n, сочетание. Число сочетаний берём готовой функцией comb из модуля math.

from math import comb

ip = [196, 138, 142, 89]     # IP-адрес узла
need = 78                    # столько адресов в подсети
ones = 18                    # ровно столько единиц в двоичной записи каждого

for m in range(1, 33):                    # m — количество единиц в маске
    bits = '1' * m + '0' * (32 - m)
    mask = [int(bits[0:8], 2), int(bits[8:16], 2), int(bits[16:24], 2), int(bits[24:32], 2)]

    b = 0                                 # единиц в адресе сети
    for i in range(4):
        b = b + bin(ip[i] & mask[i]).count('1')

    n = 32 - m                            # свободных бит
    tail = ones - b                       # столько единиц надо набрать в хвосте

    if tail >= 0 and tail <= n:
        if comb(n, tail) == need:
            print(m)

Что печатает программа

Проверка: перебрать все адреса

Если сочетания забыл, считать можно в лоб: перебрать адреса подсети и посчитать те, где единиц ровно 18. Никакой комбинаторики.

Идём от длинных масок к коротким, то есть от маленьких подсетей к большим, и на первом совпадении останавливаемся. Так перебор не успевает разрастись: до ответа он проходит всего около шестнадцати тысяч адресов.

from ipaddress import ip_network

ip = '196.138.142.89'        # IP-адрес узла
need = 78                    # столько адресов в подсети
ones = 18                    # ровно столько единиц в двоичной записи каждого

for m in range(32, 0, -1):                   # идём от самых маленьких подсетей к большим
    net = ip_network(ip + '/' + str(m), strict=False)

    count = 0
    for a in net:                            # перебираем все адреса подсети
        if bin(int(a)).count('1') == ones:
            count = count + 1

    if count == need:
        print(m)
        print(net.netmask)
        break                                # дальше подсети только больше, искать нечего

Что печатает программа

19
255.255.224.0

Проверь себя

В адресе сети 5 единиц, свободных бит 12. Сколько единиц надо набрать в хвосте, чтобы во всём адресе вышло 17?

Проверить ответ

Чему равно C(6, 2)?

Проверить ответ

Где теряют балл

Считали b по адресу узла, а не по адресу сети при этой маске.
Ответили количеством нулей, когда просили единицы.
Забыли, что C(n, t) и C(n, n − t) равны, и искали не ту строку таблицы.
Пустили перебор адресов от коротких масок: при маске /5 в подсети сто миллионов адресов.

Печать