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

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

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

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

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

731

Пояснение

Решение:

Маска 255.252.0.0 содержит 14 единиц: $252 = 11111100_2$ . Значит свободны два младших бита второго байта и оба правых байта целиком — всего 18 битов, то есть в сети $2^{18} = 262144$ адреса, а адрес сети равен 249.0.0.0.

Обозначим через $L$ количество единиц в левых двух байтах, через $R$ — в правых двух. Первый байт зафиксирован: $249 = 11111001_2$ , в нём 6 единиц. Второй байт имеет вид $000000xy$ , то есть добавляет $k$ единиц, где $k \in \{0,1,2\}$ ; значит $L = 6 + k$ . Правые два байта свободны полностью: в их 16 битах может быть от 0 до 16 единиц.

Нужно, чтобы $R \gt 2L$ . Разбираем случаи:

$k = 0$ (один вариант второго байта): $L = 6$ , нужно $R \ge 13$ , то есть $C_{16}^{13} + C_{16}^{14} + C_{16}^{15} + C_{16}^{16} = 560 + 120 + 16 + 1 = 697$ адресов;
$k = 1$ (два варианта): $L = 7$ , нужно $R \ge 15$ , то есть $16 + 1 = 17$ адресов на каждый вариант, итого 34;
$k = 2$ : $L = 8$ , нужно $R \ge 17$ — невозможно, 0 адресов.

Всего $697 + 34 = 731$ . Тот же результат даёт прямой перебор всех $2^{18}$ адресов сети.

ip   = [249, 0, 33, 87]
mask = [255, 252, 0, 0]
net  = [ip[i] & mask[i] for i in range(4)]

count = 0
for host in range(2 ** 18):
    b2 = net[1] | (host >> 16)
    b3 = (host >> 8) & 255
    b4 = host & 255
    left  = bin(net[0]).count('1') + bin(b2).count('1')
    right = bin(b3).count('1') + bin(b4).count('1')
    if right > 2 * left:
        count += 1

print(count)

Ответ: 731