Задание №13 — Маски подсети

#69804Задание №13ФИПИ

Компьютерные сети, маски подсетей

В терминологии сетей ТСР/IР маской сети называют двоичное число, которое показывает, какая часть IР-адреса узла сети относится к адресу сети, а какая — к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети. Сеть задана IР-адресом 252.67.33.87 и маской сети 255.252.0.0.
Сколько в этой сети IР-адресов, для которых в двоичной записи IР-адреса суммарное количество единиц в правых двух байтах более чем вдвое превосходит суммарное количество единиц в левых двух байтах?
В ответе укажите только число.

Правильный ответ

Пояснение

Решение:

Запишем адрес и маску в двоичном виде:

IP: $252 = 11111100_2$ , $67 = 01000011_2$ ;
маска 255.252.0.0 $= 11111111.11111100.00000000.00000000_2$ .

Адрес сети: $67 \wedge 252 = 64$ , то есть 252.64.0.0. Свободных (изменяемых) разрядов 18: два младших бита второго байта и все 16 битов третьего и четвёртого байтов.

Обозначим $L$ — число единиц в левых двух байтах, $R$ — в правых двух. Первый байт даёт 6 единиц, зафиксированная часть второго байта ( $64 = 01000000_2$ ) — ещё одну, а два свободных бита дают $k$ единиц, $k\in\{0,1,2\}$ . Значит $L = 7 + k$ , а $R$ — число единиц среди 16 свободных битов, $0\le R\le 16$ .

Условие задачи: $R \gt 2L = 14 + 2k$ .

$k=0$ (один вариант, биты 00): нужно $R\ge 15$ , таких значений $C_{16}^{15} + C_{16}^{16} = 16 + 1 = 17$ ;
$k=1$ : нужно $R \gt 16$ — невозможно;
$k=2$ : нужно $R \gt 18$ — невозможно.

Итого 17 адресов. Проверка перебором:

ones = lambda x: bin(x).count('1')
count = 0
for b2 in range(64, 68):             # 64 + два свободных бита
    for x in range(0, 65536):        # третий и четвёртый байты
        L = ones(252) + ones(b2)
        R = ones(x >> 8) + ones(x & 255)
        if R > 2 * L:
            count += 1
print(count)      # 17

Ответ: 17