Задание №13 — Количество путей в ориентированном графе

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

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

В терминологии сетей TCP/IP маской сети называют двоичное число, которое показывает, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и маске сети. Сеть задана IP-адресом 122.159.136.144 и маской сети 255.255.255.248.
Сколько в этой сети IP-адресов, для которых количество единиц в двоичной записи IP-адреса не кратно 4? В ответе укажите только число.

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

Пояснение

Решение:

Маска $255.255.255.248$ : последний байт $248_{10}=11111000_2$ , то есть под номер узла отведены 3 младших разряда. Значит, в сети $2^3 = 8$ адресов.

Адрес сети: $144_{10}=10010000_2$ , поразрядная конъюнкция с $11111000_2$ даёт $10010000_2 = 144$ . Значит, адреса сети — это 122.159.136.144, 122.159.136.145, …, 122.159.136.151.

Посчитаем единицы в двоичной записи. Первые три байта у всех адресов одинаковы: $122_{10}=01111010_2$ — 5 единиц, $159_{10}=10011111_2$ — 6 единиц, $136_{10}=10001000_2$ — 2 единицы. Вместе 13 единиц. В последнем байте старшая часть $10010$ даёт ещё 2 единицы, итого постоянных единиц 15, и к ним добавляются единицы трёх младших разрядов (от 000 до 111).

Последний байт	Младшие 3 бита	Всего единиц	Кратно 4?
144	000	15	нет
145	001	16	да
146	010	16	да
147	011	17	нет
148	100	16	да
149	101	17	нет
150	110	17	нет
151	111	18	нет

Кратно 4 количество единиц у трёх адресов, значит не кратно — у $8-3=5$ .

first = [122, 159, 136]
count = 0
for last in range(144, 152):     # 144 = 144 & 248, всего 8 адресов сети
    ones = sum(bin(b).count('1') for b in first + [last])
    if ones % 4:
        count += 1
print(count)                     # 5

Ответ: 5