Представь, что компьютерная сеть — это огромный лабиринт комнат (узлов), и каждому «компьютеру» нужно знать свой «номер комнаты» (IP-адрес), чтобы передавать друг другу записки (данные). Мы разберёмся, как эти номера выглядят, как их переводить, как вычислять «домашний» адрес комнаты (адрес сети) и «последнюю» дверь (broadcast), а также многое другое.
Не переживай, если тебя пугают «нулевые» и «единичные» миры двоичного кода. Я проведу тебя за руку, как старший товарищ, и мы всё разложим на понятные «кубики». Если где-то захочется передохнуть или вернуться к основам, сразу скажу. И в конце каждого блока ты найдёшь небольшой итог, контрольные вопросы и ссылки, куда можно заглянуть за дополнительными пояснениями.
Содержание
1. Введение и подготовка
1.1. Зачем нам нужны двоичные числа и побитовые операции
Когда ты смотришь на IP-адрес вида 192.168.5.10, на первый взгляд это просто четыре числа. Но внутри компьютер «видит» не «192» и «168», а длинную цепочку из 32 бит: 11000000.10101000.00000101.00001010. Каждый из этих битов — это «мини-коридор» в нашем лабиринте. Если мы хотим сказать «идём прямо по этим битам, меняем их, проверяем на равенство» — то нам нужны двоичные представления и операции типа AND, OR и NOT.
Аналогия: Представь, что у тебя есть плоская карта лабиринта, нарисованная как сетка «0» и «1». «1» — это стена, «0» — это проход. Побитовая операция AND — словно накладывание второй карты стен поверх первой: если в обоих местах есть стена (1), то в результате будет стена; иначе — проход. Это помогает компьютеру быстро «отсеивать» лишние пути и определять, в какой комнате (подсети) ты находишься.
На олимпиадах часто бывают задачи, где нужно быстро вычислить адрес сети, broadcast-адрес или проверить, сколько «единиц» в адресе. Чтобы сделать это без ошибок — надо понимать двоичный «язык». Поэтому первый шаг — научиться переводить десятичные числа в двоичные и обратно, а потом понять операции AND, OR, NOT на «октетах» (байтах).
1.1.1. Двоичное представление чисел
Любое число 0…255 (один октет) можно представить восемью битами. Например:
192→11000000(1·2⁷ + 1·2⁶ + 0 + 0 + 0 + 0 + 0 + 0 = 128+64).168→10101000(1·2⁷ + 0·2⁶ + 1·2⁵ + 0·2⁴ + 1·2³ + 0 + 0 + 0 = 128+32+8).5→00000101(0 + 0 + 0 + 0 + 0 + 1·2² + 0 + 1·2⁰ = 4+1).10→00001010(0 + 0 + 0 + 0 + 1·2³ + 0 + 1·2¹ + 0 = 8+2).
Чтобы перевести число N (0 ≤ N ≤ 255) в двоичный вид, можно делить его на 2 и записывать остатки, но на практике удобно использовать таблицу «2⁷, 2⁶,…, 2⁰» и вычитать. Возьми «192»: 192 ≥ 2⁷=128? Да → вычитаем 128, остаётся 64 → 64 ≥ 2⁶=64? Да → вычитаем → остаток 0. Значит, старшие два бита = 1,1, а дальше уже нули.
Обратный перевод из двоичного в десятичное — просто суммируем значения разрядов, где стоят единицы. Например: 10101000 = 1·2⁷ + 0 + 1·2⁵ + 0 + 1·2³ + 0 + 0 + 0 = 128 + 32 + 8 = 168.
1.1.2. Побитовые операции: AND, OR, NOT
Побитовая операция — как волшебство, которое «склеивает» или «разворачивает» биты:
─────────────────────────────────────────────
Побитовое AND на 8-битных октетах
─────────────────────────────────────────────
11001100 (204)
& 10101010 (170)
------------
10001000 (136)─────────────────────────────────────────────
Побитовое OR на 8-битных октетах
─────────────────────────────────────────────
11110000 (240)
| 00001111 ( 15)
------------
11111111 (255)─────────────────────────────────────────────
Побитовое NOT на одном октете
─────────────────────────────────────────────
NOT 10110010 (178)
---------------
01001101 ( 77)
─────────────────────────────────────────────
Побитовое XOR на 8-битных октетах
─────────────────────────────────────────────
11001010 (202)
⊕
10111000 (184)
------------
01110010 (114)
- AND (конъюнкция):
1 AND 1 → 1, иначе →0. Представь, что у тебя две маски, и на пересечении прозрачных участков (1) остаётся прозрачный пиксель, иначе — чёрный. - OR (дизъюнкция):
1 OR 0 → 1,0 OR 0 → 0. Это как если хотя бы одна маска прозрачна, получаем прозрачный пиксель. - NOT (инверсия):
NOT 1 → 0,NOT 0 → 1. Это как переключатель: там, где было «проход» (0), делаем «стену» (1), и наоборот.
Пример: 10101100 AND 11110000 = 10100000. Это пригодится, когда мы хотим отделить «сетевые» биты от «хостовых».
Итог раздела «Двоичные числа и побитовые операции»
- Умение: переводить числа 0–255 ↔ 8-битовые двоичные.
- Умение: выполнять AND, OR, NOT на байтах.
- Ты готов двигаться дальше: наступило время познакомиться с самим IP-адресом и маской подсети.
Контрольные вопросы
- Что такое двоичное представление числа 200?
- Какой результат
10101111 (двоичное число) OR 10010000 (двоичное число)? - Что делает операция NOT на бите
0?
Блок заданий 1. Двоичное представление и побитовые операции
Задание 1.1. Переведите три октета
a = 200, b = 180, c = 10в 8-битный двоичный вид, выполните побитовое OR и верните результат в десятичном виде.
Задание 1.2.
- Вариант 1: даны два октета
x = 120, y = 13. Вычислите~xи~y(8-битно), выведите максимальное.- Вариант 2: даны
x = 123, y = 200и маскаm = 15. Вычислитеx & mиy & m, затем инвертируйте результат (8-битно) и выведите максимум.
Задание 1.3.
- Загадка A: маска
M_A = 200(11001000₂). Найдите всеn ∈ [0…255], для которыхn & M_Aимеет ровно 3 единицы.- Загадка B: маска
M_B = 45(00101101₂). Найдите всеn ∈ [0…255], для которыхn & M_Bимеет не менее 2 единиц.
Задание 1.4. (челлендж «побитовые битвы»)
Для трёх конкретных масок выполнить следующие подсчёты:
- Маска
15(00001111₂), условие: ровно 2 единицы.
Переберитеn ∈ [0…255], вычислитеn & 15, посчитайте число единиц. Сколькоnдают ровно 2 единицы? Сколько всего такихn?- Маска
85(01010101₂), условие: ровно 2 единицы.
Переберитеn ∈ [0…255], вычислитеn & 85, посчитайте число единиц. Сколькоnдают ровно 2 единицы?- Маска
170(10101010₂), условие: ровно 2 единицы.
Переберитеn ∈ [0…255], вычислитеn & 170, посчитайте число единиц. Сколькоnдают ровно 2 единицы?В конце сложите три полученных числа и укажите общий результат (суммарное число
nдля всех трёх масок).
Задание 1.5. (исправь чужой ответ)
Даны три «неправильных» решения для задачи 1.2 Вариант 1 и 2. В каждом решении допущена ровно одна ошибка. Найдите эту ошибку и кратко объясните:— Решение A1: x = 100, y = 50 ~100 = 155, ~50 = 205 Ответ: 248 — Решение A2: x = 100, y = 50, m = 15 x&m = 100&15 = 4, y&m = 50&15 = 2 ~4 = 251, ~2 = -3 → вывод: 251
Ответы
Задание 1.1 Ввод: 200 180 10 Вывод: 254 Задание 1.2 — Вариант 1: Пример: x = 120, y = 13 → ~120 = 135, ~13 = 242 → вывод 242 — Вариант 2: Пример: x = 123, y = 200, m = 15 → x&m = 11, y&m = 8, затем ~11 = 244, ~8 = 247 → вывод 247 Задание 1.3 — Загадка A: M_A = 200 → n∈[200…231] (всего 32 числа) — Загадка B: M_B = 45 → 176 чисел (перечислять не нужно) Задание 1.4 — Маска 15: ровно 2 единицы в (n & 15) → 96 значений. — Маска 85: ровно 2 единицы в (n & 85) → 96 значений. — Маска 170: ровно 2 единицы в (n & 170) → 96 значений. Итого: 96 + 96 + 96 = 288 Задание 1.5 — A1: Ошибка — вместо вывода «205» дописали «248». — A2: Ошибка — неправильно инвертировалиy & m:~2 = -3, не 253? В решении вывели 251.
Подсказки/Решения на Python
# Упражнение 1.1
def or_octets(a: int, b: int, c: int) -> int:
return a | b | c
# Пример:
# print(or_octets(12, 85, 34)) # → 87
# Упражнение 1.2
def variant1(x: int, y: int) -> int:
return max((~x) & 0xFF, (~y) & 0xFF)
def variant2(x: int, y: int, m: int) -> int:
return max(((x & m) ^ 0xFF) & 0xFF, ((y & m) ^ 0xFF) & 0xFF)
# Примеры:
# print(variant1(100, 50)) # → 205
# print(variant2(170, 85, 240)) # → 175
# Упражнение 1.3
def puzzle_A():
M = 200
return [n for n in range(256) if bin(n & M).count('1') == 3] # [200..231]
def puzzle_B():
M = 45
return [n for n in range(256) if bin(n & M).count('1') >= 2] # len = 176
# print(len(puzzle_A()), puzzle_A())
# print(len(puzzle_B()))
# Упражнение 1.4
def count_mask_exact2(mask: int) -> int:
return sum(1 for n in range(256) if bin(n & mask).count('1') == 2)
masks = [15, 85, 170]
results = [count_mask_exact2(m) for m in masks]
total = sum(results)
# → results = [96, 96, 96], total = 288
# Упражнение 1.5 — текстовые объяснения, Python не требуется.
2. Структура IPv4-адреса и маска подсети
2.1. Что такое IP-адрес и зачем он нужен
Представь гигантский офис с тысячей кабинетов. Каждый компьютер — как сотрудник, сидящий в своём кабинете. Чтобы отправить письмо (пакет данных), нужно знать точный «номер кабинета». В интернете этот номер называется IP-адрес. В IPv4 он записывается как четыре числа от 0 до 255, разделённые точками (x.x.x.x), — это совсем как адрес «3 этаж, кабинет 52». Но внутри компьютер хранит его в двоичном виде: b₃₁…b₀ (32 бита).
Пример: 192.168.5.10 → в двоичном виде 11000000.10101000.00000101.00001010. Первые 8 бит «11000000» означают 192, и так далее.
Разбиение на 4 октета (в двоичном виде):
192 . 168 . 10 . 23
11000000.10101000.00001010.00010111Но есть не только «номер кабинета», есть ещё «коридор» или «этаж»: мы разбиваем весь мир адресов на подсети (сети), чтобы компьютерам было проще находить друг друга. Для этого используется маска подсети.
2.2. Маска подсети: «сколько битов отводим под сеть, сколько под хост»
Маска подсети — это тоже 32-битная «цепочка» из единиц и нулей. Сначала идут n единиц (они «фиксируют» часть адреса как адрес сети), а потом идут 32−n нулей (они означают «пространство» для хостов). Записывается она двумя способами:
- CIDR-нотация:
/n, гдеn— число единиц. Например,/24. - Точечная запись: четыре октета от 0 до 255. Например,
255.255.255.0.
Примеры соответствия:
/24=11111111.11111111.11111111.00000000=255.255.255.0. Подсеть: первые 24 бита — «сетевые», последние 8 бит — «хостовые» (на 256 адресов, но 254 хоста)./29=11111111.11111111.11111111.11111000=255.255.255.248. Оставляет 3 бита «хостовых» → 8 адресов, но 6 доступных хостов.
───────────────────────────────────────────────────────────────────
Маска подсети (/26)
───────────────────────────────────────────────────────────────────
Десятичный вид: 255 . 255 . 255 . 192
(октет 1) (2) (3) (4)
Двоичный вид: 11111111 . 11111111 . 11111111 . 11000000
└─────┬─┘ └────┬─┘ └───────┬───┘└─┬──┘
сеть сеть сеть сеть сеть хост
(бит 26) (6 бит)
<─────── сеть (26 бит) ───────────>
<хост(6 бит)>
───────────────────────────────────────────────────────────────────
Зачем это нужно? Если маска
/24, то первые три октета задают сеть (например,192.168.5.*), а последний октет выбирает «кабинет» внутри этой сети (0…255). Но адреса192.168.5.0считается «адресом сети», а192.168.5.255— «широковещательным» (broadcast), их нельзя давать конкретным компьютерам.
2.3. Как найти адрес сети и broadcast
Для любого IP-адреса и маски подсети мы можем вычислить:
- Адрес сети =
IP AND mask(побитовая конъюнкция). Он «обнуляет» все хостовые биты. Это как найти «номер этажа» без указания комнаты:192.168.5.10 AND 255.255.255.0 = 192.168.5.0. - Широковещательный адрес (broadcast) =
(IP AND mask) OR (NOT mask). Это «последний» адрес в подсети, где все хостовые биты = 1. Например,192.168.5.0 OR 0.0.0.255 = 192.168.5.255. - Диапазон хостов — это адреса от
(network + 1)до(broadcast − 1). В случае/24это192.168.5.1…192.168.5.254. - Количество адресов =
2^(32−n)(включая network и broadcast). Доступных хостов =2^(32−n) − 2.
──────────────────────────────────────────────────────────────────────────────────────────
Адрес сети и широковещательный адрес
──────────────────────────────────────────────────────────────────────────────────────────
1) Вычисление сетевого адреса (Network Address):
IP-адрес 192 . 168 . 5 . 10
Двоичный вид IP: 11000000 . 10101000 . 00000101 . 00001010
Маска подсети 255 . 255 . 255 . 0
Двоичный вид маски: 11111111 . 11111111 . 11111111 . 00000000
───────────────────────────────────────────────────────────────────────
Побитовое AND (IP & Маска) = Сетевой адрес:
11000000 . 10101000 . 00000101 . 00001010
AND 11111111 . 11111111 . 11111111 . 00000000
= 11000000 . 10101000 . 00000101 . 00000000
Сетевой адрес (десятичный): 192.168.5.0
«Как найти «номер этажа» без указания комнаты»:
192.168.5.10 AND 255.255.255.0 = 192.168.5.0
──────────────────────────────────────────────────────────────────────────────────────────
2) Вычисление широковещательного адреса (Broadcast Address):
Сетевой адрес (Network): 192 . 168 . 5 . 0
Двоичный вид сети: 11000000 . 10101000 . 00000101 . 00000000
«Обратная» маска (Wildcard): 0 . 0 . 0 . 255
Двоичный «Not маски»: 00000000 . 00000000 . 00000000 . 11111111
───────────────────────────────────────────────────────────────────────
Побитовое OR (Сеть | Wildcard) = Broadcast:
11000000 . 10101000 . 00000101 . 00000000
OR 00000000 . 00000000 . 00000000 . 11111111
= 11000000 . 10101000 . 00000101 . 11111111
Широковещательный адрес: 192.168.5.255
«Последний» адрес в подсети, где все хостовые биты = 1:
192.168.5.0 OR 0.0.0.255 = 192.168.5.255
──────────────────────────────────────────────────────────────────────────────────────────
3) Диапазон хостов (Host Range):
Для /24 (маска 255.255.255.0) диапазон:
Сетевой адрес + 1 = 192.168.5.0 + 1 → 192.168.5.1
Broadcast − 1 = 192.168.5.255 − 1 → 192.168.5.254
Диапазон доступных хостов: 192.168.5.1 … 192.168.5.254
──────────────────────────────────────────────────────────────────────────────────────────
4) Подсчёт количества адресов:
Общее количество адресов в подсети = 2^(32 − n)
Для /24: 2^(32 − 24) = 2^8 = 256 адресов (включая network и broadcast)
Доступных хостов = 2^(32 − n) − 2
Для /24: 256 − 2 = 254 хоста
──────────────────────────────────────────────────────────────────────────────────────────
Шаги решения задачи «вычислить сеть и broadcast» (пример):
- Понять условие: дан IP и маска (в любой форме).
- Перевести IP и маску в двоичную форму (или работать с десятичными октетами, если знаешь эквивалент).
- Выполнить
ANDпо октетам: получаем адрес сети. - Выполнить
ORадреса сети с инверсией маски (где маска = 0 → ставим 1): получаем broadcast. - Записать ответ в привычном формате
x.x.x.x.
2.3.1. Пример решения
Задача: Найдите сеть и broadcast для IP 10.23.45.67 с маской 255.255.248.0 (/21).
- Переводим IP в двоичные октеты:
10 = 00001010 23 = 00010111 45 = 00101101 67 = 01000011 IP = 00001010.00010111.00101101.01000011 - Маска
/21в двоичном виде:11111111.11111111.11111000.00000000 = 255.255.248.0 - Адрес сети =
IP AND mask:00001010.00010111.00101101.01000011 AND 11111111.11111111.11111000.00000000 = 00001010.00010111.00101000.00000000 = 10.23.40.0 - Broadcast =
(IP AND mask) OR (NOT mask):IP AND mask = 00001010.00010111.00101000.00000000 (10.23.40.0) NOT mask = 00000000.00000000.00000111.11111111 (0.0.7.255) OR 00001010.00010111.00101000.00000000 00000000.00000000.00000111.11111111 = 00001010.00010111.00101111.11111111 = 10.23.47.255 - Диапазон хостов:
10.23.40.1…10.23.47.254(всего 2¹¹−2 = 2046 хостов).
2.4. Итог раздела «Структура IPv4 и маска подсети»
- Ты умеешь представлять IPv4-адрес в виде четырёх октетов и в виде 32 бит.
- Понимаешь, что маска
/n= первыеnбит «сетевые», а остальные «хостовые». - Умеешь вычислять адрес сети (
IP AND mask) и broadcast ((IP AND mask) OR NOT mask). - Знаешь, сколько адресов есть в подсети
/n(и сколько доступных хостов).
Контрольные вопросы
- Что такое адрес сети и зачем он нужен? (Ответ:
IP AND mask, определяет подсеть.) - Как вычислить broadcast-адрес по IP и маске? (Ответ:
(IP AND mask) OR NOT mask.) - Сколько хостов доступно в сети
/28? (Ответ:2^(32−28) − 2 = 16−2 = 14.)
Блок заданий 2. Вычисление сети и широковещательного адреса
Задание 2.1. Даны IP
x₁.x₂.x₃.x₄(например,192.168.5.100) и маскаm₁.m₂.m₃.m₄(например,255.255.255.192). Найдите сетевой адрес и broadcast.
Задание 2.2.
Задание A: IP =
10.23.45.67, маска =/28. Найдите network, broadcast, диапазон хостов.Задание B: IP =
172.31.200.15, маска =255.255.255.240. Найдите network, broadcast, диапазон хостов.
Задание 2.3. Дан IP =
8.8.8.8и маска =/22. Выведите сначала общее число адресов в сети, затем число доступных хостов (без network и broadcast).
Задание 2.4. (исправь чужую ошибку)
Найдено неверное решение для IP =130.45.78.34, маска =255.255.252.0(автор написал, что общее число адресов = 1024, хостов = 1023). Найдите ошибку и дайте правильные числа: общее число адресов = ?, число доступных хостов = ?, последний хост = ?
Ответы
Задание 2.1 Ввод: 192.168.5.100 255.255.255.192 Вывод: 192.168.5.64 192.168.5.127 Задание 2.2 — A: Ввод: 10.23.45.67 /28 Вывод: 10.23.45.64 10.23.45.79 10.23.45.65–10.23.45.78 — B: Ввод: 172.31.200.15 255.255.255.240 Вывод: 172.31.200.0 172.31.200.15 172.31.200.1–172.31.200.14 Задание 2.3 Ввод: 8.8.8.8 /22 Вывод: 1024 1022 Задание 2.4 Исправление: — неверно вычли число доступных хостов (с учётом сети и broadcast вычитают 2, а не 1). Правильно: общее количество = 1024, доступных хостов = 1022, последний хост = 130.45.79.254.
Подсказки/Решения на Python
import ipaddress
# Задание 2.1
def network_broadcast(ip_str: str, mask_str: str):
net = ipaddress.IPv4Network(f"{ip_str}/{mask_str}", strict=False)
return str(net.network_address), str(net.broadcast_address)
# Пример:
# print(network_broadcast("192.168.5.100", "255.255.255.192"))
# → ("192.168.5.64", "192.168.5.127")
# Задание 2.2
def full_range(ip_str: str, mask_str: str):
net = ipaddress.IPv4Network(f"{ip_str}/{mask_str}", strict=False)
first = list(net.hosts())[0]
last = list(net.hosts())[-1]
return str(net.network_address), str(net.broadcast_address), f"{first}–{last}"
# Примеры:
# print(full_range("10.23.45.67", "28"))
# → ("10.23.45.64", "10.23.45.79", "10.23.45.65–10.23.45.78")
# print(full_range("172.31.200.15", "255.255.255.240"))
# → ("172.31.200.0", "172.31.200.15", "172.31.200.1–172.31.200.14")
# Задание 2.3
def count_addresses(ip_str: str, mask_str: str):
net = ipaddress.IPv4Network(f"{ip_str}/{mask_str}", strict=False)
total = net.num_addresses
hosts = total - 2
return total, hosts
# Пример:
# print(count_addresses("8.8.8.8", "22"))
# → (1024, 1022)
# Задание 2.4
def corrected_values(ip_str: str, mask_str: str):
net = ipaddress.IPv4Network(f"{ip_str}/{mask_str}", strict=False)
total = net.num_addresses
hosts = total - 2
last = str(list(net.hosts())[-1])
return total, hosts, last
# Пример:
# print(corrected_values("130.45.78.34", "255.255.252.0"))
# → (1024, 1022, "130.45.79.254")
Дополнительный блок: Работа с модулем ipaddress и побитовыми операциями в Python
Чтобы не «теряться в битах» и быстро проверять свои рассуждения, очень удобно использовать Python и стандартный модуль ipaddress. В этом блоке мы покажем, как с его помощью:
- Создавать и анализировать сети (
IPv4Network). - Перебирать доступные хосты (
hosts()). - Вычислять
network_address,broadcast_address, длину префикса (prefixlen), общее число адресов (num_addresses). - Подсчитывать число единиц/нулей в адресе (
bit_count(), смещение и маскирование).
Возможности класса ipaddress.IPv4Address и побитовые операции
Класс IPv4Address из модуля ipaddress удобен для преобразований IP-адресов между «человекочитаемым» видом (x.x.x.x), целым числом и двоичным представлением. Кроме того, с помощью «побитовых» операций можно находить адрес сети, broadcast, проверять принадлежность к сети и решать другие задачи. Ниже — основные приёмы и примеры.
1. Создание объекта IPv4Address из строки и из целого числа
import ipaddress
# 1) Из строкового представления ("x.x.x.x"):
ip_str = ipaddress.IPv4Address('192.168.5.10')
print(ip_str) # 192.168.5.10
print(type(ip_str)) # <class 'ipaddress.IPv4Address'>
# 2) Из целого числа (0…2**32-1):
# Пример: '192.168.5.10' ⇄ 3232235786
num = 3232235786
ip_from_int = ipaddress.IPv4Address(num)
print(ip_from_int) # 192.168.5.10
print(int(ip_from_int)) # 3232235786
2. Двоичное представление адреса
# Получить «сырой» 32-битный номер:
ip = ipaddress.IPv4Address('192.168.5.10')
x = int(ip) # 3232235786
# Двоичная строка ровно из 32 бит с ведущими нулями:
b32 = format(x, '032b') # '11000000101010000000010100001010'
print(b32)
# Разбиение на 8-битные «октеты»:
octets = [b32[i:i+8] for i in range(0, 32, 8)]
print(octets) # ['11000000', '10101000', '00000101', '00001010']
3. Подсчёт единиц и нулей через строки
# Используем двоичную строку, а не bit_count()
ip = ipaddress.IPv4Address('192.168.5.10')
x = int(ip)
# Получаем 32-битную строку:
b32 = format(x, '032b') # '11000000101010000000010100001010'
# Считаем единицы и нули в 32-битной строке:
ones_total = b32.count('1')
zeros_total = b32.count('0')
print("32-бит как строка:", b32)
print("ones:", ones_total, "zeros:", zeros_total)
# Сколько единиц/нулей в «левых» и «правых» 16 битах:
left16_str = b32[:16]
right16_str = b32[16:]
ones_left = left16_str.count('1')
zeros_left = left16_str.count('0')
ones_right = right16_str.count('1')
zeros_right = right16_str.count('0')
print("левая половина 16 бит:", left16_str)
print("правая половина 16 бит:", right16_str)
print("ones_left:", ones_left, "zeros_left:", zeros_left)
print("ones_right:", ones_right, "zeros_right:", zeros_right)
4. Создание маски /n как битовой строки и преобразование в int
Вместо «сдвигов» можно наглядно собрать двоичную маску, а потом перевести её в целое.
# Пример: маска /24 = 24 единицы, потом 8 нулей
n = 24
mask_bin_str = '1' * n + '0' * (32 - n) # '11111111111111111111111100000000'
mask_int = int(mask_bin_str, 2) # преобразуем из двоичной строки в int
print("Битовая строка маски /24:", mask_bin_str)
print("Маска /24 как int (hex):", hex(mask_int)) # 0xffffff00
# Вычисляем адрес сети и broadcast для IP = 192.168.5.10:
ip = ipaddress.IPv4Address('192.168.5.10')
x = int(ip)
# Адрес сети = IP & mask_int
network_int = x & mask_int
# Broadcast = network_int | (инверсия маски)
# Инверсия: меняем все «1» на «0» и наоборот, но ограничиваем 32 бита
wildcard_int = int('0' * n + '1' * (32 - n), 2)
broadcast_int = network_int | wildcard_int
network_ip = ipaddress.IPv4Address(network_int)
broadcast_ip = ipaddress.IPv4Address(broadcast_int)
print("IP:", ip)
print("Mask /24 int:", hex(mask_int))
print("Network int:", network_int, "→", network_ip) # 192.168.5.0
print("Broadcast int:", broadcast_int, "→", broadcast_ip) # 192.168.5.255
Пояснение:
- Мы сначала строим строку из 24 «1» и 8 «0», затем
int(..., 2)переводит её в целое. - «Инверсия» маски для broadcast делается также строкой:
'0'*24 + '1'*8. - Такой способ более нагляден для новичков, чем побитовые сдвиги
<<и>>.
5. Поиск /L по двум IP (через строки)
# Задача: по IP1 и IP2 найти максимальный L, чтобы они в одной подсети
import ipaddress
def find_max_prefix_str(ip1_str, ip2_str):
# Получаем 32-битные строки для обоих IP:
s1 = format(int(ipaddress.IPv4Address(ip1_str)), '032b')
s2 = format(int(ipaddress.IPv4Address(ip2_str)), '032b')
# Сколько старших бит совпадает подряд?
L = 0
for b1, b2 in zip(s1, s2):
if b1 == b2:
L += 1
else:
break
# Теперь проверяем, чтобы IP не совпадал с сетью и broadcast.
# Будем уменьшать L, пока не найдём допустимую маску.
while L >= 0:
# Строим строковую маску длины L:
mask_str = '1' * L + '0' * (32 - L)
mask_int = int(mask_str, 2)
net1_int = int(ipaddress.IPv4Address(ip1_str)) & mask_int
broadcast_int = net1_int | (int('0' * L + '1' * (32 - L), 2))
ip1_int = int(ipaddress.IPv4Address(ip1_str))
ip2_int = int(ipaddress.IPv4Address(ip2_str))
if (ip1_int not in (net1_int, broadcast_int) and
ip2_int not in (net1_int, broadcast_int) and
(int(ipaddress.IPv4Address(ip2_str)) & mask_int) == net1_int):
return L
L -= 1
return 0
# Тест:
print(find_max_prefix_str('157.220.185.237', '157.220.184.230')) # Ожидаем 23
Краткий вывод по возможностям IPv4Address
- Можно создавать из строки (
'x.x.x.x') или из целого (0…2³²−1). - Метод
int(ip)возвращает 32-битный номер. - Через
format(int(ip), '032b')получаем ровно 32 бита «0/1». - Через строки (
count('1')/count('0')) легко считать единицы и нули. - Создавать маску
/nможно бинарной строкой'1'*n + '0'*(32-n)иint(..., 2). - «Инверсия» маски (wildcard) — это
'0'*n + '1'*(32-n), тоже переводим вint. - С помощью операций
&и|получаем адрес сети и broadcast без «дополнительного кода» Python.
Контрольные вопросы блока «IPv4Address и побитовые операции через строки»
- Как получить 32-битную строку из объекта
IPv4Address? (Ответ:format(int(ip), '032b').) - Как сосчитать количество «1» и «0» в 32-битной строке? (Ответ:
b32.count('1')иb32.count('0').) - Как создать битовую маску
/nстрокой? (Ответ:'1'*n + '0'*(32-n).) - Как получить адрес сети из IP
ipи маскиmask_int? (Ответ:int(ip) & mask_int.) - Как получить broadcast, если известен
network_intиL? (Ответ:network_int | int('0'*L + '1'*(32-L), 2).) - Почему при инверсии маски побитовые операции безопаснее делать через строки? (Ответ: чтобы не зависеть от «дополнительного кода» Python и не обрезать потом
& 0xFFFFFFFF.)
IPv4Network и работа с сетью в Python
- Импортируем модуль и создаём сеть
import ipaddress # Если у нас есть IP сети и префикс: net1 = ipaddress.IPv4Network('192.168.5.0/24', strict=False) # Или если нам дали IP узла + mask: net2 = ipaddress.IPv4Network('10.23.45.67/21', strict=False) # Если дали IP сети + wildcard: wildcard = '0.0.7.255' # Инвертируем wildcard → обычная маска: mask_octets = [255 - int(x) for x in wildcard.split('.')] mask_str = '.'.join(str(x) for x in mask_octets) # '255.255.248.0' net3 = ipaddress.IPv4Network(f'172.16.80.0/{mask_str}', strict=False)Пояснение:
strict=Falseпозволяет создавать сеть даже по «узловому» IP (не строго по адресу сети).- В случае wildcard-маски мы сначала формируем «маску сети» путём вычитания каждого октета из 255.
- Получаем основные свойства
print("Адрес сети:", net1.network_address) # Например, 192.168.5.0 print("Broadcast:", net1.broadcast_address) # 192.168.5.255 print("Длина префикса:", net1.prefixlen) # 24 print("Общее число адресов:", net1.num_addresses) # 256 print("Доступных хостов:", len(list(net1.hosts()))) # 254 (от начала до конца без network и broadcast)Пояснение:
network_addressиbroadcast_addressвозвращают объектыIPv4Address. Их можно сразу печатать или конвертировать вstr.prefixlen— это число «единиц» в маске (/n).num_addressesвозвращает всех адресов сети (включая network и broadcast).- Чтобы получить только «хостовые» адреса, нужно писать
list(net1.hosts())или итерироватьfor ip in net1.hosts():.
- Перебор хостов и подсчёт битов
# Задача: сколько в сети 172.16.80.0/21 адресов, где popcount % 3 != 0? import ipaddress net = ipaddress.IPv4Network('172.16.80.0/21') # /21 = 255.255.248.0 count = 0 for ip in net.hosts(): # Преобразуем IP в число: num = int(ip) # Считаем единицы: ones = num.bit_count() if ones % 3 != 0: count += 1 print("Результат:", count) # Выведет точное число # Пример: сравнение «нулей слева < нулей справа»: def zeros_left(ip_obj): x = int(ip_obj) left16 = x >> 16 return 16 - left16.bit_count() def zeros_right(ip_obj): x = int(ip_obj) right16 = x & 0xFFFF return 16 - right16.bit_count() net2 = ipaddress.IPv4Network('159.242.0.0/23', strict=False) valid_ips = [ip for ip in net2.hosts() if zeros_left(ip) < zeros_right(ip)] print("Число адресов, где zeros_left < zeros_right:", len(valid_ips))Пояснение:
int(ip)преобразует объектIPv4Addressв целое число (0…2³²−1).bit_count()(Python 3.8+) возвращает число единиц в двоичной записи.- Чтобы получить «левые» 16 бит, мы делим на 2¹⁶ (или делаем
x >> 16); «правые» 16 бит получаем черезx & 0xFFFF.
- Пример: поиск
/Lпо двум IP (смотри раздел 5, что такое/L)# Задача: по IP1 и IP2 найти максимальный L, чтобы они в одной подсети import ipaddress def find_max_prefix(ip1_str, ip2_str): ip1_int = int(ipaddress.IPv4Address(ip1_str)) ip2_int = int(ipaddress.IPv4Address(ip2_str)) diff = ip1_int ^ ip2_int if diff == 0: # IP1 == IP2, можно взять /32, но network == host, и нет хостов return 32 # номер старшего отличающегося бита (от 0 до 31 справа) p = diff.bit_length() - 1 L = 31 - p # Проверяем, что IP1 и IP2 ≠ network и ≠ broadcast для /L while L >= 0: mask_int = int('1' * L + '0' * (32-L)) network = ip1_int & mask_int broadcast = network | (~mask_int & 0xFFFFFFFF) if ip1_int not in (network, broadcast) and ip2_int not in (network, broadcast): return L L -= 1 return 0 # В крайнем случае /0 (весь IPv4) # Тест: print(find_max_prefix('157.220.185.237', '157.220.184.230')) # Должно вывести 23Пояснение:
diff = ip1_int ^ ip2_intотмечает все биты, где адреса отличаются.bit_length()→ позиция старшего бита «1» вdiff.L = 31 − (bit_length() − 1)даёт длину префикса, при которой совпадают старшие биты.- Если один из IP оказался равен network или broadcast, уменьшаем
Lна 1 и проверяем снова.
Побитовые операции «на пальцах» в Python
Помимо bit_count(), нам часто нужны:
<<(сдвиг влево): умножение на 2k, перемещает биты в старшую сторону.>>(сдвиг вправо): целочисленное деление на 2k, отбрасывает младшие биты.&(побитовое AND): обнуляет биты, где в одном из операндов = 0.|(побитовое OR): устанавливает бит = 1, если в хотя бы одном операнде = 1.^(побитовое XOR): устанавливает бит = 1, если биты операндов различаются.~(побитовое NOT): инверсия всех битов (но результат в Python — «дополнительный код», поэтому явно берём& 0xFFFFFFFFдля 32 бит).
──────────────────────────────────────────────────────────────────
Побитовые сдвиги (<< и >>)
──────────────────────────────────────────────────────────────────
1) Исходное значение (8-битовый бинарный октет):
0 0 1 0 1 1 0 1 (00101101₂ = 45₁₀)
──────────────────────────────────────────────────────────────────
2) Сдвиг влево на 1 бит (<< 1):
- Все биты «двигаются» на одну позицию влево.
- Самый левый бит «выпадает», справа добавляется 0.
0 0 1 0 1 1 0 1 ← исходные биты
└┬──────────────
│ сдвиг влево на 1
⌄
0 1 0 1 1 0 1 0 (01011010₂ = 90₁₀)
• 00101101₂ << 1 = 01011010₂
• Десятичные эквиваленты: 45 << 1 = 90
──────────────────────────────────────────────────────────────────
3) Сдвиг вправо на 1 бит (>> 1):
- Все биты «двигаются» на одну позицию вправо.
- Самый правый бит «выпадает», слева добавляется 0.
0 0 1 0 1 1 0 1 ← исходные биты
└──────────────┬─
│ сдвиг вправо на 1
⌄
0 0 0 1 0 1 1 0 (00010110₂ = 22₁₀)
• 00101101₂ >> 1 = 00010110₂
• Десятичные эквиваленты: 45 >> 1 = 22# Примеры побитовых операций:
x = 0b101100 # 44 в десятичном
# Сдвиг влево на 2 бита:
print(bin(x << 2)) # 0b10110000 = 176 # Сдвиг вправо на 3 бита: print(bin(x >> 3)) # 0b101 = 5
# AND с маской 0b11110000:
mask = 0b11110000
print(bin(x & mask)) # 0b10000 = 16
# OR с 0b00001111:
print(bin(x | 0b00001111)) # 0b101111 = 47
# XOR с 0b111111:
print(bin(x ^ 0b111111)) # 0b101 = 5
# NOT (инверсия) в 8 битах:
print(bin((~x) & 0xFF)) # инвертирует только младшие 8 бит
# Пример: создаём маску /n как целое:
n = 23
mask_int = ((1 << n) - 1) << (32 - n) & 0xFFFFFFFF
print("Маска /23 в двоичном:", bin(mask_int)) # 0b11111111.11111111.11111110.00000000
Кратко:
x << kперемещает битыxвлево наkпозиций.x >> kделитxна2<sup>k</sup>, отсекая последниеkбит.x & mask«обнуляет» битыx, гдеmask= 0.~xинвертирует все биты, но в Python нужно «отрезать» 32 бита через& 0xFFFFFFFF.
Дополнительный блок: Инверсия бит в 32-битном представлении
Когда мы вычисляем broadcast или wildcard-маску, нам нужно «инвертировать» все биты маски сети (превратить единицы в нули и нули в единицы) именно в пределах 32 бит. В Python оператор ~ (побитовое NOT) не ограничен 32 битами — он работает в «дополнительном коде» и даёт бесконечное расширение, поэтому после ~ нужно обрезать до ровно 32 бит через & 0xFFFFFFFF. Это гарантирует, что остаются только младшие 32 бита.
1. Зачем нужна инверсия 32-битно?
- Если у нас есть маска сети
/n, например255.255.255.0(/24), двоично это11111111.11111111.11111111.00000000. Чтобы получить wildcard, мы меняем каждый бит:00000000.00000000.00000000.11111111→0.0.0.255. - Чтобы вычислить broadcast напрямую, часто берут
network_int | wildcard_int, гдеwildcard_int— это «инверсия» маски. - Важно: Python не хранит целые числа строго в 32 битах, поэтому
~mask_intдаст отрицательное число, у которого «старшие» биты тоже «1». Чтобы оставить только младшие 32 бита, нужно применить& 0xFFFFFFFF.
2. Пример: инверсия через побитовую операцию ~ и «обрезка»
import ipaddress
# Маска /24 через двоичную строку:
mask_bin_str = '1' * 24 + '0' * 8 # '11111111111111111111111100000000'
mask_int = int(mask_bin_str, 2) # 0xFFFFFF00 = 4294967040
print("mask_int (деcт):", mask_int) # 4294967040
print("mask_int (hex):", hex(mask_int)) # 0xffffff00
# Попробуем просто инвертировать:
raw_inversion = ~mask_int
print("~mask_int (деcт):", raw_inversion) # -4294967041 (отрицательное!)
print("~mask_int (bin):", bin(raw_inversion))
# Здесь bin выдаст: '-0b100000000000000000000000000000001'
# Чтобы оставить только младшие 32 бита, делаем & 0xFFFFFFFF:
inv32 = raw_inversion & 0xFFFFFFFF
print("inv32 (деcт):", inv32) # 255
print("inv32 (hex):", hex(inv32)) # 0x000000ff
print("inv32 (bin 32 бит):", format(inv32, '032b'))
# '00000000000000000000000011111111' → 0.0.0.255
Пояснение:
~mask_intдаёт отрицательное число — Python расширяет «масштаб» бита до бесконечности (дополнительный код).& 0xFFFFFFFF(«AND с 32 единицами») «обрезает» лишние старшие биты и оставляет только младшие 32 бита.- В результате
inv32— это ровно 32-битная инверсия исходной маски: двоично00000000.00000000.00000000.11111111.
3. Вычисление broadcast с помощью инверсии через строки
Для новичков ещё проще представить инверсию не через ~, а через строку: составляем «wildcard» как '0'*n + '1'*(32−n), а потом переводим в int. Ниже оба способа:
# Пусть IP = 192.168.5.10, префикс /24
ip = ipaddress.IPv4Address('192.168.5.10')
x = int(ip) # 3232235786
n = 24
# 1) Через двоичную строку:
wildcard_str = '0'*n + '1'*(32 - n) # '00000000000000000000000011111111'
wildcard_int_str = int(wildcard_str, 2) # 255
# 2) Через ~mask_int & 0xFFFFFFFF:
mask_str = '1'*n + '0'*(32 - n) # '11111111111111111111111100000000'
mask_int = int(mask_str, 2) # 4294967040
wildcard_int_bitwise = (~mask_int) & 0xFFFFFFFF # тоже 255
print("wildcard_int_str:", wildcard_int_str) # 255
print("wildcard_int_bitwise:", wildcard_int_bitwise) # 255
# Адрес сети:
network_int = x & mask_int # 3232235786 & 4294967040 = 3232235780
network_ip = ipaddress.IPv4Address(network_int) # 192.168.5.0
# Broadcast = network_int | wildcard_int
broadcast_int = network_int | wildcard_int_str # 3232235780 | 255 = 3232236035
broadcast_ip = ipaddress.IPv4Address(broadcast_int) # 192.168.5.255
print("Network:", network_ip) # 192.168.5.0
print("Broadcast:", broadcast_ip) # 192.168.5.255
4. Краткий итог
- Простейшая «инверсия» маски через строки:
'0'*n + '1'*(32−n)→int(..., 2). - Если всё же используете
~mask_int, всегда «обрезайте» через& 0xFFFFFFFF, чтобы получить ровно 32-битное значение. - Без
& 0xFFFFFFFFPython вернёт отрицательное число с «дополнительным кодом» за пределами 32 бит. - Из полученной «инверсии» (wildcard_int) легко вычислить broadcast:
broadcast_int = network_int | wildcard_int.
Практика: пошаговые битовые операции с IPv4-адресами
В этом разделе мы подробно разберём, как «по частям» работать с числовым представлением IPv4-адреса: получать маску и wildcard из префикса, разбивать адрес на октеты и половины, а также считать единицы и нули с помощью битовых сдвигов и побитовых операций. Постараемся объяснять очень доступно, чтобы казалось как «строить из конструкторов».
1. Получаем маску /n и wildcard через битовые сдвиги, AND и NOT
──────────────────────────────────────────────────────────────────────────
Пошаговое образование сетевой маски из формулы
mask = (((1 << n) - 1) << (32 - n)) & 0xFFFFFFFF, где n — префикс
──────────────────────────────────────────────────────────────────────────
Шаг 1. Вычисляем (1 << n)
Операция «1 << n» сдвигает единицу влево на n позиций.
В двоичном виде (32 бита) это:
1 << n = 00000000 00000000 00000000 00000001
<< n бит
------------------------------------------------
(единица на позиции n, слева от LSB)
Пример (n = 26) Было:
1 << 26 = 00000000 00000000 00000000 00000001
<< 26
= 00000000 00000000 00000001 00000000 00000000
(в 32-битовом представлении:
двоично: 00000000 00000000 00000001 00000000 00000000)
──────────────────────────────────────────────────────────────────────────
Шаг 2. Вычитаем 1: (1 << n) – 1
Вычитание «– 1» превращает «000…0100…0» (с единственной 1 на позиции n)
в n единиц в младших битах:
(1 << n) = 00000000 00000000 00000001 00000000 00000000
– 1 = 00000000 00000000 00000000 11111111 11111111
--------------------------------------------------------------
(1 << n) – 1 = 00000000 00000000 00000000 11111111 11111111
│ │
│ └— последние n бит = 1
└— старшие (32−n) бит = 0
Пример (n = 26) Было:
1 << 26 = 00000000 00000000 00000001 00000000 00000000
– 1 = 00000000 00000000 00000000 11111111 11111111
--------------------------------------------------------------
(1 << 26) – 1 = 00000000 00000000 00000000 11111111 11111111
(в двоичном: 00000000 00000000 00000000 11111111 11111111)
(это 26 единиц в младших битах)
──────────────────────────────────────────────────────────────────────────
Шаг 3. Сдвигаем влево на (32 − n): ((1 << n) – 1) << (32 − n)
Берём блок из n единиц (в младших битах) и сдвигаем его на (32−n) позиций влево,
чтобы единицы заняли старшие n битов, а младшие (32−n) обнулились:
(1⋅…⋅1)ₙбита (младшие) = 00000000 00000000 00000000 11111111 11111111
<< (32 − n)
--------------------------------------------------------------
((1 << n) – 1) << (32 − n) = 11111111 11111111 11111111 11000000 00000000
│ │ │ │ │ │
└— n единиц в старших разрядах └— (32−n) нулей
Пример (n = 26 → 32−26 = 6) Было:
(1 << 26) – 1 = 00000000 00000000 00000000 11111111 11111111
(26 единиц в младших битах)
<< 6
--------------------------------------------------------------
Результат = 11111111 11111111 11111111 11000000 00000000
(26 единиц слева) (6 нулей справа)
В двоичной форме: 11111111 . 11111111 . 11111111 . 11000000
В шестнадцатеричном: 0xFFFFFFC0
──────────────────────────────────────────────────────────────────────────
Шаг 4. Побитовое И с 0xFFFFFFFF: … & 0xFFFFFFFF
Маска 0xFFFFFFFF в двоичном: 11111111 11111111 11111111 11111111
Операция «& 0xFFFFFFFF» гарантирует, что результат останется в 32-битовом
представлении без знаковых расширений.
11111111 11111111 11111111 11000000 00000000 ((1<<n)–1)<< (32−n)
AND 11111111 11111111 11111111 11111111 11111111 (0xFFFFFFFF)
-----------------------------------------------------------
11111111 11111111 11111111 11000000 00000000 (итоговые 32 бита)
Пример (n = 26)Было:
((1<<26) – 1) << 6 = 11111111 11111111 11111111 11000000 00000000
& 0xFFFFFFFF = 11111111 11111111 11111111 11111111 11111111
--------------------------------------------------------------
mask = 11111111 11111111 11111111 11000000 00000000
(в двоичном) → 255.255.255.192 (в десятичном)
──────────────────────────────────────────────────────────────────────────
Итоговая маска (32-битный результат):
11111111 . 11111111 . 11111111 . 11000000
255 . 255 . 255 . 192
(соответствует префиксу /26)
──────────────────────────────────────────────────────────────────────────
- Задача: по префиксу
/n(например,n = 20) получить числовые значения маски сети и wildcard-маски, используя битовые операции. - Напомним, что IPv4-адрес — это 32-битное число. Маска
/nозначает: первыеnбит = 1, остальные32-nбит = 0.
Например,/20→ двоично11111111.11111111.11110000.00000000. - Шаг 1. Строим маску
/nчерез битовые сдвиги.- Делаем «1» повторённую
nраз:(1 << n) - 1. Например,n=20→1<<20 = 2<sup>20</sup>, вычитаем 1 → получается число с 20 единицами:
0b11111111111111111111(20 бит). - Чтобы эти «20 единиц» оказались на самых старших (левых) битах 32-битного слова, сдвигаем влево на
32 - nпозиций:
mask_int = ((1 << n) - 1) << (32 - n). - В Python результат может быть больше 32 бит (в «дополнительном коде»), поэтому для строго 32-битного результата берём младшие 32 бита:
mask_int = (((1 << n) - 1) << (32 - n)) & 0xFFFFFFFF.
- Делаем «1» повторённую
- Пример на Python:
n = 20 mask_int = (((1 << n) - 1) << (32 - n)) & 0xFFFFFFFF print("Маска /20 (int):", mask_int) print("Маска /20 (hex):", hex(mask_int)) print("Маска /20 (bin 32 бит):", format(mask_int, '032b')) # Ожидаем: 0b11111111111111111111000000000000 → 255.255.240.0Пояснение:
(1 << 20) - 1даёт0b11111111111111111111(20 единиц, остро внизу).>>> (32 - 20) = 12задаёт, что «20 единиц» сдвигаются влево, чтобы заполнить старшие 20 бит из 32.& 0xFFFFFFFFпозволяет оставить только младшие 32 бита (на случай, если промежуточный результат вышел за 32 бита).
- Шаг 2. Получаем wildcard (инверсия маски).
- Wildcard-маска = побитовая инверсия маски сети: все «1» → «0», все «0» → «1». В пределах 32 бит это удобно сделать так:
wildcard_int = (~mask_int) & 0xFFFFFFFF— оператор
~инвертирует все биты, но Python хранит числа в «дополнительном коде» бесконечной длины, поэтому сразу обрезаем младшие 32 бита& 0xFFFFFFFF. - Таким образом, если маска
/20=11111111.11111111.11110000.00000000(двоично), то wildcard =00000000.00000000.00001111.11111111.
- Wildcard-маска = побитовая инверсия маски сети: все «1» → «0», все «0» → «1». В пределах 32 бит это удобно сделать так:
- Пример на Python:
wildcard_int = (~mask_int) & 0xFFFFFFFF print("Wildcard /20 (int):", wildcard_int) print("Wildcard /20 (hex):", hex(wildcard_int)) print("Wildcard /20 (bin 32 бит):", format(wildcard_int, '032b')) # Ожидаем: 0b00000000000000000000111111111111 → 0.0.15.255
2. Разбиваем IPv4-адрес (целое число) на октеты и «половины» через сдвиги и AND
────────────────────────────────────────────────────────────────────────────────
Получаем октеты IP-адреса из 32-битного числа x
────────────────────────────────────────────────────────────────────────────────
Пусть x = 3232235786 (это 192.168.1.10 в десятичном виде)
В 32-битном двоичном представлении:
x = 3232235786₁₀ = 11000000 10101000 00000001 00001010₂
Разбиваем на октеты через сдвиги и маску 0xFF:
1) octet1 = (x >> 24) & 0xFF
x >> 24 = 00000000 00000000 00000000 11000000₂ = 0x000000C0 = 192₁₀
& 0xFF = 00000000 00000000 00000000 11000000₂ = 0x000000C0 = 192₁₀
→ octet1 = 192
Шаги:
11000000 10101000 00000001 00001010 (x)
└─────── сдвиг вправо на 24 бита ────────▶ 00000000 00000000 00000000 11000000
& 0xFF
Результат: 00000000 00000000 00000000 11000000 → 192
────────────────────────────────────────────────────────────────────────────────
2) octet2 = (x >> 16) & 0xFF
x >> 16 = 00000000 00000000 11000000 10101000₂ = 0x0000C0A8 = 49320₁₀
& 0xFF = 00000000 00000000 00000000 10101000₂ = 0x000000A8 = 168₁₀
→ octet2 = 168
Шаги:
11000000 10101000 00000001 00001010 (x)
└─────── сдвиг вправо на 16 бит ───────▶ 00000000 00000000 11000000 10101000
& 0xFF
Результат: 00000000 00000000 00000000 10101000 → 168
────────────────────────────────────────────────────────────────────────────────
3) octet3 = (x >> 8) & 0xFF
x >> 8 = 00000000 11000000 10101000 00000001₂ = 0x00C0A801 = 12582913₁₀
& 0xFF = 00000000 00000000 00000000 00000001₂ = 0x00000001 = 1₁₀
→ octet3 = 1
Шаги:
11000000 10101000 00000001 00001010 (x)
└─────── сдвиг вправо на 8 бит ───────▶ 00000000 11000000 10101000 00000001
& 0xFF
Результат: 00000000 00000000 00000000 00000001 → 1
────────────────────────────────────────────────────────────────────────────────
4) octet4 = x & 0xFF
x = 11000000 10101000 00000001 00001010₂ = 0xC0A8010A = 3232235786₁₀
& 0xFF = 00000000 00000000 00000000 11111111₂ = 0x000000FF = 255₁₀
Результат = 00000000 00000000 00000000 00001010₂ = 10₁₀
→ octet4 = 10
Шаги:
11000000 10101000 00000001 00001010 (x)
& 0xFF ▶ 00000000 00000000 00000000 00001010
Результат: 00000000 00000000 00000000 00001010 → 10
────────────────────────────────────────────────────────────────────────────────
Итого: IP-адрес x = 3232235786₁₀ → октеты (192, 168, 1, 10)
3232235786 → [octet1 = 192] . [octet2 = 168] . [octet3 = 1] . [octet4 = 10]
────────────────────────────────────────────────────────────────────────────────
Предположим, у нас есть объект IPv4Address или просто целое x = int(ip). Мы хотим «достать» каждый из четырёх октетов (по 8 бит) и «половины» (левые/правые 16 бит).
- Пусть
ip = '192.168.5.10'→x = int(ip):
import ipaddress ip = ipaddress.IPv4Address('192.168.5.10') x = int(ip) # x = 3232235786 - Получаем четырёхоктетный вид через сдвиги и AND:
octet1(первый, старший байт) =(x >> 24) & 0xFF.
Почему?x >> 24сдвигает все биты вправо на 24, оставляя только старшие 8 бит в младших 8 позициях, а& 0xFFотбросит всё, что старше 8 бит (остаток гарантированно ≤255).octet2(второй байт) =(x >> 16) & 0xFF.
x >> 16оставляет старшие 16 бит в младших 16 позициях, а& 0xFF«отрезает» все, кроме тех, что в диапазоне 0–255, т. е. второй октет.octet3(третий байт) =(x >> 8) & 0xFF.
Аналогично.octet4(четвёртый, младший байт) =x & 0xFF.
Без сдвига «отрезаем» лишь младшие 8 бит.
- Пример на Python:
octet1 = (x >> 24) & 0xFF octet2 = (x >> 16) & 0xFF octet3 = (x >> 8) & 0xFF octet4 = x & 0xFF print("IP целое:", x) print("Октеты:", octet1, octet2, octet3, octet4) # 192 168 5 10 - Получаем «лучшую половину» (левые 16 бит) и «правую половину» (младшие 16 бит):
left16 = x >> 16— сдвигаем вправо на 16, оставляем старшие 16 бит;left16получается от 0 до 65535.right16 = x & 0xFFFF— маска0xFFFF(16 единиц) оставляет только младшие 16 бит.
- Пример на Python:
left16 = x >> 16 right16 = x & 0xFFFF print("left16 (десятичное):", left16) print("left16 (двоичное 16 бит):", format(left16, '016b')) print("right16 (десятичное):", right16) print("right16 (двоичное 16 бит):", format(right16, '016b'))
3. Подсчёт единиц и нулей через побитовые сдвиги и bit_count, bit_length
Есть несколько способов узнать, сколько «1» и «0» в двоичном представлении:
- Через метод
bit_count()(Python 3.8+):ones_total = x.bit_count()— число всех «1» в 32-битномx.zeros_total = 32 - ones_total— оставшиеся биты «0», если мы считаем ровно 32 бита.
- Через битовые сдвиги «на пальцах»: перебираем все 32 бита:
ones = 0 zeros = 0 temp = x # копируем, чтобы не испортить x for i in range(32): if temp & 1: # смотрим младший бит (0 или 1) ones += 1 else: zeros += 1 temp = temp >> 1 # сдвигаем вправо, «удаляем» младший бит print("ones:", ones, "zeros:", zeros)Пояснение:
temp & 1проверяет, равен ли младший (нулевой) бит единице (1) или нулю (0).- После проверки делаем
temp >>= 1, чтобы на следующей итерации проверить уже следующий бит. - Так мы «прогоняем» все 32 бита.
- Через
bit_length()полезно узнать, сколько «знаковых» бит задействовано:bit_length()возвращает номер старшего (последнего «1») бита + 1. Например,
0b10110.bit_length()= 5 (10110имеет длину 5).- Но для IPv4 нам часто нужна именно длина 32 бита, поэтому обычно используют
format(x, '032b')илиbit_count().
- Сравнение «левых 16 бит» и «правых 16 бит»: сколько «1»/«0» в каждой половине?
- Получаем
left16 = x >> 16,right16 = x & 0xFFFF(как в предыдущем разделе). ones_left = left16.bit_count(),zeros_left = 16 - ones_left(точно 16 бит).ones_right = right16.bit_count(),zeros_right = 16 - ones_right.
- Получаем
Пример «всё вместе» на Python
import ipaddress
# Пусть IP:
ip = ipaddress.IPv4Address('203.0.113.45')
x = int(ip)
print("IP:", ip)
print("32-бит (bin):", format(x, '032b'))
# 1) Маска /18 и wildcard:
n = 18
mask_int = (((1 << n) - 1) << (32 - n)) & 0xFFFFFFFF wildcard_int = (~mask_int) & 0xFFFFFFFF print("Mask /18 (int):", mask_int, "(", format(mask_int, '032b'), ")") print("Wildcard /18 (int):", wildcard_int, "(", format(wildcard_int, '032b'), ")") # 2) Разбиваем IP на октеты: octet1 = (x >> 24) & 0xFF
octet2 = (x >> 16) & 0xFF
octet3 = (x >> 8) & 0xFF
octet4 = x & 0xFF
print("Октеты:", octet1, octet2, octet3, octet4)
# 3) Берём левую и правую половины:
left16 = x >> 16
right16 = x & 0xFFFF
print("left16 (bin):", format(left16, '016b'))
print("right16 (bin):", format(right16, '016b'))
# 4) Считаем единицы/нули разными способами:
ones_total = x.bit_count()
zeros_total = 32 - ones_total
print("Всего ones (bit_count):", ones_total, "zeros:", zeros_total)
# Через ручной перебор бит:
ones_manual = 0
zeros_manual = 0
temp = x
for _ in range(32):
if temp & 1:
ones_manual += 1
else:
zeros_manual += 1
temp >>= 1
print("Всего ones (ручной):", ones_manual, "zeros:", zeros_manual)
# В левой половине:
ones_left = left16.bit_count()
zeros_left = 16 - ones_left
# В правой половине:
ones_right = right16.bit_count()
zeros_right = 16 - ones_right
print("ones_left:", ones_left, "zeros_left:", zeros_left)
print("ones_right:", ones_right, "zeros_right:", zeros_right)
# 5) bit_length() — показывает, сколько бит до первого '1' слева:
print("bit_length(x):", x.bit_length(),
"(IP без ведущих нулей в двоичном виде занимает столько бит)")Итоговый вывод
- Чтобы получить маску
/nчерез битовые сдвиги:
mask_int = (((1 << n) - 1) << (32 - n)) & 0xFFFFFFFF. - Чтобы инвертировать маску (wildcard), используем
wildcard_int = (~mask_int) & 0xFFFFFFFF. Это «обрезает» лишние биты после~. - Октеты извлекаются через
(x >> 24)&0xFF,(x >> 16)&0xFF,(x >> 8)&0xFF,x & 0xFF. - «Левая половина» (старшие 16 бит) =
x >> 16; «правая половина» =x & 0xFFFF. - Число единиц можно получить
x.bit_count()или «вручную» через перебор&1и>>=1в цикле. bit_length()возвращает «длину» числа без ведущих нулей (сколько бит до первого «1» слева).
Краткий итог блока
- Ты знаешь, как с помощью
ipaddress.IPv4Networkбыстро получать network, broadcast, число хостов и перебирать хосты. - Умеешь считать «единицы» и «нули» в адресе Python-методом
bit_count(). - Понимаешь, как создавать маску
/nчерез побитовые операции (<<, >>, &, |, ~). - Готов применять комбинированный метод «аналитика + Python» для любой сети.
Контрольные вопросы блока «Python и битовые операции»
- Как создать объект
IPv4Networkпо IP узла и маске? (Пример:IPv4Network('10.23.45.67/21', strict=False).) - Как получить список всех хостов в сети
net? (Ответ:list(net.hosts()).) - Как посчитать число единиц в адресе
ip? (Ответ:int(ip).bit_count().) - Как составить маску
/23как целое число? (Ответ:((1 << 23) - 1) << 9 & 0xFFFFFFFF.) - Как получить «левые 16 бит» и «правые 16 бит» в
x = int(ip)? (Ответ:left16 = x >> 16,right16 = x & 0xFFFF.)
Ссылки для углублённого изучения
Задания: Работа с модулем ipaddress и побитовыми операциями
Задание D1.
1) Создайте объектIPv4Addressпо строке'10.0.5.17'.
2) Преобразуйте его в целое число и обратно в объектIPv4Address.
3) Выведите двоичное представление этого числа ровно в 32 бита.
Задание D2.
Дан объектip = IPv4Address('192.168.100.9').
1) Получите 32-битную строку черезformat(int(ip), '032b').
2) Разбейте её на четыре восьмибитных «октета» и выведите их как список строк.
3) Посчитайте количество единиц и нулей во «левой половине» (первые 16 бит) и «правой половине» (последние 16 бит).
Задание D3.
Сформируйте маску/19двумя способами:
- Через побитовые сдвиги:
mask_int = ((1 << 19) - 1) << (32 - 19) & 0xFFFFFFFF.- Через двоичную строку:
mask_int_str = int('1'*19 + '0'*13, 2).После этого, для IP
'172.16.23.45'вычислите:
1) Адрес сети:network_int = int(ip) & mask_intи выведите какIPv4Address(network_int).
2) Wildcard-маску: инверсиюmask_intна 32 бита и выведите какIPv4Address(wildcard_int).
3) Broadcast:broadcast_int = network_int | wildcard_intи выведите какIPv4Address(broadcast_int).
Задание D4.
1) Создайте сетьnet = IPv4Network('10.10.0.0/22', strict=False).
2) Выведите:
—net.network_address
—net.broadcast_address
—net.prefixlen
—net.num_addresses
— количество «хостов» (len(list(net.hosts()))).
3) Подсчитайте, сколько хостов в этой сети имеют общее число единиц (bit_count()) нечетным.
Задание D5.
По двум IP-адресам'203.0.113.17'и'203.0.113.98'найдите максимальныйL(целое 0…32), при котором они оба попадают в одну подсеть/Lи ни один не совпадает с network или broadcast.
Алгоритм:
- Переведите оба IP в 32-битные строки через
format(int(...), '032b').- Найдите длину общего префикса
L(сколько старших бит подряд совпадает).- Пока
L ≥ 0проверяйте, не совпадают ли эти IP с network или broadcast для/L(вычисляйте маску из строки'1'*L + '0'*(32-L)).- Если совпадает — уменьшайте
Lна 1 и повторяйте, иначе выводитеL.
Ответы
Ответ D1.
1) ip_obj = IPv4Address('10.0.5.17')
2) num = int(ip_obj) → 167773457
ip_back = IPv4Address(num) → '10.0.5.17'
3) format(num, '032b') → '00001010 00000000 00000101 00010001'
Ответ D2.
1) b32 = '11000000101010000001100100001001'
2) ['11000000', '10101000', '01100100', '00001001']
3) left16 = '1100000010101000' → ones_left = 6, zeros_left = 10
right16 = '0001100100001001' → ones_right = 5, zeros_right = 11
Ответ D3.
1) Побитово:
mask_int = ((1<<19)-1) << 13 & 0xFFFFFFFF = 0xFFFFE000 → mask_int = 0xFFFFE000 = 4294963200 2) Через строку: mask_int_str = int('1'*19 + '0'*13, 2) → тоже 4294963200 3) Для IP = '172.16.23.45': x = int(IPv4Address('172.16.23.45')) = 2886722568 network_int = x & mask_int = 2886722560 → IPv4Address = '172.16.0.0' wildcard_int = (~mask_int) & 0xFFFFFFFF = 2047 → IPv4Address = '0.0.31.255' broadcast_int = network_int | wildcard_int = 2886724607 → '172.16.31.255' Ответ D4. net = IPv4Network('10.10.0.0/22'): network_address = '10.10.0.0' broadcast_address = '10.10.3.255' prefixlen = 22 num_addresses = 1024 len(hosts) = 1022 Количество хостов с нечетным bit_count: 512 Ответ D5. IP1 = '203.0.113.17', IP2 = '203.0.113.98': 32-битные строки: s1 = '11001011000000000001100100010001' s2 = '11001011000000000001100101100010' Старших совпадающих бит = 25 → L = 25 Проверка: ни один IP ≠ network / broadcast для /25 → вывод: 25
Подсказки/Решения на Python
import ipaddress
# --- Решение D1 ---
# 1)
ip_obj = ipaddress.IPv4Address('10.0.5.17')
# 2)
num = int(ip_obj)
ip_back = ipaddress.IPv4Address(num)
# 3)
b32 = format(num, '032b')
print(ip_obj, num, ip_back, b32)
# --- Решение D2 ---
ip2 = ipaddress.IPv4Address('192.168.100.9')
b32_2 = format(int(ip2), '032b')
octets = [b32_2[i:i+8] for i in range(0, 32, 8)]
left16 = b32_2[:16]
right16 = b32_2[16:]
ones_left = left16.count('1')
zeros_left = left16.count('0')
ones_right = right16.count('1')
zeros_right = right16.count('0')
print(b32_2, octets, ones_left, zeros_left, ones_right, zeros_right)
# --- Решение D3 ---
# Побитовые сдвиги:
n = 19
mask_int = ((1 << n) - 1) << (32 - n) & 0xFFFFFFFF # Через строку: mask_int_str = int('1'*n + '0'*(32 - n), 2) print(mask_int, mask_int_str) ip3 = ipaddress.IPv4Address('172.16.23.45') x3 = int(ip3) network_int = x3 & mask_int wildcard_int = (~mask_int) & 0xFFFFFFFF broadcast_int = network_int | wildcard_int print(ip3, ipaddress.IPv4Address(network_int), ipaddress.IPv4Address(wildcard_int), ipaddress.IPv4Address(broadcast_int)) # --- Решение D4 --- net4 = ipaddress.IPv4Network('10.10.0.0/22', strict=False) print(net4.network_address, net4.broadcast_address, net4.prefixlen, net4.num_addresses, len(list(net4.hosts()))) count_odd = sum(1 for ip in net4.hosts() if int(ip).bit_count() % 2 == 1) print("Нечётных единиц:", count_odd) # --- Решение D5 --- def find_max_prefix_str(ip1_str, ip2_str): s1 = format(int(ipaddress.IPv4Address(ip1_str)), '032b') s2 = format(int(ipaddress.IPv4Address(ip2_str)), '032b') L = 0 for b1, b2 in zip(s1, s2): if b1 == b2: L += 1 else: break while L >= 0:
mask_str = '1' * L + '0' * (32 - L)
mask_int = int(mask_str, 2)
net1_int = int(ipaddress.IPv4Address(ip1_str)) & mask_int
wildcard_int = int('0' * L + '1' * (32 - L), 2)
broadcast_int = net1_int | wildcard_int
ip1_int = int(ipaddress.IPv4Address(ip1_str))
ip2_int = int(ipaddress.IPv4Address(ip2_str))
if (ip1_int not in (net1_int, broadcast_int) and
ip2_int not in (net1_int, broadcast_int) and
(ip2_int & mask_int) == net1_int):
return L
L -= 1
return 0
print(find_max_prefix_str('203.0.113.17', '203.0.113.98')) # → 25
3. Wildcard-маски
3.1. Почему нужна wildcard-маска
В олимпиадных задачах иногда дают не «обычную» маску, а wildcard-маску (она ещё называется «маской переменных»). Если в «сетевой» маске бит равен 1 → этот бит фиксирован (выбирает сеть), а в wildcard-маске такие биты = 0 (тоже «фиксация»). Но где в маске был 0 → в wildcard = 1 (может «меняться»). Это как отрицание привычной маски: wildcard = NOT (сетевая mask). Зачем? Во многих задачах удобнее сначала показать «диапазон» изменяющихся бит, а потом по ним считать условия.
Аналогия: Если маска сети говорит: «Эти двери всегда закрыты (>1), а эти могут открываться (0)», то wildcard-маска говорит наоборот: «Эти двери точно открыты (>1)? Нет, а эти точно закрыты/открыты (>1)? Давай считать наоборот». На практике нам нужно «инвертировать» маску, чтобы понять, какие биты можно варьировать.
3.2. Как работать с wildcard: перевод в обычную маску и вычисление диапазона
- Дана wildcard-маска
w1.w2.w3.w4. Чтобы получить сетевую маску, делаем «инверсию» каждого октета:
mask_octet = 255 − wildcard_octet. Например, еслиwildcard = 0.0.7.255, тоmask = 255.255.248.0. - Теперь используем обычный алгоритм (см. раздел 2):
- Адрес сети =
IP AND mask. - Broadcast =
(IP AND mask) OR wildcard(ведь wildcard уже =NOT mask). - Диапазон хостов =
network + 1 … broadcast − 1.
- Адрес сети =
- Запомним, что IP сети и сам broadcast-адрес не используются для узлов.
────────────────────────────────────────────────────────────────────────
Инверсия маски и wildcard
────────────────────────────────────────────────────────────────────────
Маска подсети (/21):
Десятичный: 255 . 255 . 248 . 0
Двоичный : 11111111 . 11111111 . 11111000 . 00000000
Инверсия битов (NOT)
↓ ↓
Wildcard (обратная маска):
Десятичный: 0 . 0 . 7 . 255
Двоичный : 00000000 . 00000000 . 00000111 . 11111111
────────────────────────────────────────────────────────────────────────
Чтобы получить маску из wildcard:
00000000 . 00000000 . 00000111 . 11111111
↑ ↑ ↑ ↑
| | | |
Инвертировать все биты (NOT)
| | | |
↓ ↓ ↓ ↓
11111111 . 11111111 . 11111000 . 00000000
Десятичный: 255 . 255 . 248 . 0 → Маска
────────────────────────────────────────────────────────────────────────
3.2.1. Пример решения задания
Условие: Сеть задана IP-адресом 172.16.80.0 и wildcard-маской 0.0.7.255. Сколько IP-адресов в этой сети имеют число единиц в двоичной записи не кратное 3? Ответ дать числом.
- Инвертируем wildcard → маска:
0 → 255,7 → 248,255 → 0:mask = 255.255.248.0(/21).
- Адрес сети =
172.16.80.0/21.- Всего
2^(32−21) = 2048адресов, из них2046хостовых (без сети и broadcast).
- Всего
- Нужно посчитать, сколько среди этих хостов
bin(int(ip)).count("1") % 3 ≠ 0.import ipaddress net = ipaddress.IPv4Network('172.16.80.0/21') cnt = 0 for ip in net.hosts(): if bin(int(ip)).count('1') % 3 != 0: cnt += 1 print(cnt) # ответ - Аналитически можно заметить, что «фиксированных» единиц в IP сети =
popcount(172.16.80)=popcount(10101100.00010000.01010)= 9. Остаётся 11 «хостовых» бит, и мы перебираем значения 0…2047, но уже проверяем, чтобы(9 + popcount(host_bits)) % 3 ≠ 0. Тогда считаем через биномиальные коэффициенты или программно.
3.3. Итог раздела «Wildcard-маски»
- Ты знаешь, что wildcard =
NOT mask. - Умеешь переводить wildcard → обычная маска (
mask_octet = 255 − wildcard_octet). - Умеешь находить network =
IP AND maskи broadcast =(IP AND mask) OR wildcard. - Понимаешь, что network и broadcast не могут быть адресами хостов.
Контрольные вопросы
- Что такое wildcard-маска и как она связана с сетевой маской? (Ответ: wildcard =
NOT mask.) - Как получить сетевую маску, если дана wildcard
0.0.7.255? (Ответ:255.255.248.0.) - Какой адрес broadcast для
10.10.32.0с wildcard0.0.15.255? (Решение: mask =255.255.240.0, network =10.10.32.0, broadcast =10.10.47.255.)
Дополнительные материалы
- Статья «Что такое wildcard-маска?» на examplenetwork.site.
3. Wildcard-маски
Задание 3.1. Даны сетевой IP
172.16.80.0и wildcard0.0.7.255. Найдите эквивалентную сетевую маску/n, первый и последний хост.
Задание 3.2. Тот же пример: сеть
172.16.80.0, wildcard0.0.7.255. Сколько хостов (без сети и broadcast) имеют число единиц в 32-битном представлении не кратное 3?
Задание 3.3.
- Задача C: IP =
10.10.32.0, wildcard =0.0.15.255. Найдите/n, число хостов и сколько из них имеют чётное число нулей в 32-битном представлении.- Задача D: IP =
100.100.56.0, wildcard =0.0.7.255. Найдите/n, число хостов и сколько из них имеют нечётное число единиц в 32-битном представлении.
Задание 3.4.
- Задача E1: IP =
192.168.0.0, wildcard =0.0.1.255. Найдите/n, число хостов и сколько из них имеют чётное число единиц.- Задача E2: IP =
192.168.0.0, wildcard =0.0.3.255. Найдите/n, число хостов и сколько из них имеют чётное число единиц.
Ответы
Задание 3.1 Ввод: 172.16.80.0 0.0.7.255 Вывод: /21 172.16.80.1 172.16.87.254 Задание 3.2 Ввод: 172.16.80.0 0.0.7.255 Вывод: 1364 Задание 3.3 — C: Ввод: 10.10.32.0 0.0.15.255 Вывод: /20 4094 2048 — D: Ввод: 100.100.56.0 0.0.7.255 Вывод: /21 2046 1023 Задание 3.4 — E1: Ввод: 192.168.0.0 0.0.1.255 Вывод: /23 510 255 — E2: Ввод: 192.168.0.0 0.0.3.255 Вывод: /22 1022 512
Подсказки/Решения на Python
import ipaddress
# Задание 3.1
def from_wildcard(ip_str: str, wildcard_str: str):
w = ipaddress.IPv4Address(wildcard_str)
mask_int = (~int(w)) & (2**32 - 1)
prefix = ipaddress.IPv4Network((ip_str, mask_int), strict=False).prefixlen
net = ipaddress.IPv4Network(f"{ip_str}/{prefix}", strict=False)
first = list(net.hosts())[0]
last = list(net.hosts())[-1]
return prefix, str(first), str(last)
# Пример:
# print(from_wildcard("172.16.80.0", "0.0.7.255"))
# → (21, "172.16.80.1", "172.16.87.254")
# Задание 3.2
def count_non_multiple_of_3(ip_str: str, wildcard_str: str):
w = ipaddress.IPv4Address(wildcard_str)
mask_int = (~int(w)) & (2**32 - 1)
net = ipaddress.IPv4Network((ip_str, mask_int), strict=False)
return sum(1 for ip in net.hosts() if bin(int(ip)).count('1') % 3 != 0)
# Пример:
# print(count_non_multiple_of_3("172.16.80.0", "0.0.7.255"))
# → 1364
# Задание 3.3
def scenario_C():
p, first, last = from_wildcard("10.10.32.0", "0.0.15.255")
net = ipaddress.IPv4Network(f"10.10.32.0/{p}", strict=False)
even_zeros = sum(
1 for ip in net.hosts()
if (16 - (int(ip) & 0xFFFF).bit_count()) % 2 == 0
)
return p, net.num_addresses - 2, even_zeros
def scenario_D():
p, first, last = from_wildcard("100.100.56.0", "0.0.7.255")
net = ipaddress.IPv4Network(f"100.100.56.0/{p}", strict=False)
odd_ones = sum(
1 for ip in net.hosts()
if bin(int(ip)).count('1') % 2 == 1
)
return p, net.num_addresses - 2, odd_ones
# Примеры:
# print(scenario_C()) # → (20, 4094, 2048)
# print(scenario_D()) # → (21, 2046, 1023)
# Задание 3.4
def scenario_E(flag: int):
if flag == 1:
w = ipaddress.IPv4Address("0.0.1.255")
else:
w = ipaddress.IPv4Address("0.0.3.255")
mask_int = (~int(w)) & (2**32 - 1)
net = ipaddress.IPv4Network(("192.168.0.0", mask_int), strict=False)
total_hosts = net.num_addresses - 2
even_pop = sum(1 for ip in net.hosts() if bin(int(ip)).count('1') % 2 == 0)
return net.prefixlen, total_hosts, even_pop
# Примеры:
# print(scenario_E(1)) # → (23, 510, 255)
# print(scenario_E(2)) # → (21, 2046, 1024)
4. Подсчёт единиц и нулей в IPv4-адресах
4.1. Зачем считать биты
В олимпиадных и ЕГЭ-задачах часто встречаются условия на «количество единиц» или «количество нулей» в адресе. Например: «сравните число нулей в левых двух октетах и число нулей в правых двух октетах». Или «найдите, сколько адресов в сети имеют сумму единиц не кратную 5». Понимание, как быстро посчитать «popcount» (количество единиц), или «zeroscount» в 16 или 32 битах, — это must-have в твоём арсенале.
Аналогия: Представь, что у каждых «чекпойнтов» (битов) есть лампочка: включена (1) или выключена (0). Задача может звучать так: «В той половине (левая часть IP, первые два октета) лампочек выключено меньше, чем справа». Чтобы проверить это для всех адресов в подсети, нужно уметь быстро подсчитывать, сколько лампочек зажжено и сколько нет.
4.2. Методы подсчёта единиц/нулей
- Ручной способ (для маленьких префиксов
/28, /29):- Берём октет, переводим в двоичный, считаем количество «1» (или «0»).
- Для двух октетов:
left16 = (ip_int >> 16),right16 = ip_int & 0xFFFF. Затемpopcount = bin(left16).count("1")иbin(right16).count("1").
- Программный способ (Python):
-
import ipaddress # Чтобы получить целое число из IP: ip = ipaddress.IPv4Address('192.168.5.10') x = bin(int(ip))[2:] left16_pop = x[:16].count('1') left16_zeros = 16 - left16_pop # Правые 16 бит: right16_pop = x[16:].count('1') right16_zeros = 16 - right16_pop
-
- Ускоренный перебор (для больших префиксов
/21, /22):- Не нужно перебирать все 2¹¹ или 2¹⁰ хостов «по одному», если есть аналитическая формула (например, биномиальные коэффициенты). Но на олимпиадах бывает допустимо «неполное» тестирование через Python, если знаешь, что диапазон не слишком большой.
Шаги решения «условия на нули слева и справа»:
- Понять, как вычисляется
left16иright16(см. примеры выше). - Вычислить для «наихудшего» адреса внутри подсети (тот, у которого левых «0» будет максимально или наоборот) и убедиться, что условие выполняется для всех.
- Если перебором: итерируем
for ip in net.hosts():и проверяемzeros_left < zeros_rightилиzeros_left ≤ zeros_right, в зависимости от условия задачи.
Иногда достаточно проверить только два крайних адреса внутри подсети (т. е. «network+1» и «broadcast−1»), если понятно, что именно эти комбинации дают «наихудший» вариант по условию. Но важно понимать, почему именно они «худшие».
4.2.1. Пример задачи (упрощённо)
Условие (упрощённое): Дана подсеть /23. В ней IP вида 159.242.A.223, нужно найти максимальное A (0…255), чтобы для ВСЕХ IP в этой подсети выполнялось zeros_left < zeros_right.
Шаги аналитического решения:
Подсчёт «нулей» и «единиц» в подсети /23
(задача: найти максимальный A, чтобы во всех IP:
zeros_left < zeros_right)
┌────────────────────────────────────────────────────────────────────────────────────────┐
│ 1. Параметры исходной подсети: │
│ • Маска /23 → dotted-decimal: 255.255.254.0 │
│ • В двоичном виде маска /23: │
│ │
│ 11111111.11111111.11111110.00000000 │
│ ─────── ─────── ─────── ─────── │
│ <-16 бита-><-7 бит--><<-9 бита---> │
│ «фиксированная» часть «сетевой» «хостовая» │
│ (первые 16 бит) (3-й октет) (1 бит 3-го + 8 бит 4-го октета) │
└────────────────────────────────────────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────────────────────────────────────────┐
│ 2. Структура IP внутри этой /23: │
│ │
│ IP = 159.242.A.223 → как двоичное 32-битное число: │
│ │
│ [ 159 ] [ 242 ] [ (A & 254) ] [ host_bits ] │
│ ┌────────┐ ┌────────┐ ┌───────────┐ ┌─────────────┐ │
│ │10011111│ │11110010│ │xxxxxxx0 │ │ hhhhhhhh │ h = хостовые биты │
│ │ (159) │ │ (242) │ │(A&254): 7 сетевых │ последний бит 3-го октета + 8 бит 4-го │
│ └────────┘ └────────┘ └───────────┘ └─────────────┘ │
│ ↑ ↑ ↑ ↑ │
│ │ │ │ │ │
│ │ │ │ └── «host_bits» (9 бит: 1 сетевой + 8хост)│
│ │ │ │ • последний бит 3-го октета │
│ │ │ │ • все 8 бит 4-го октета │
│ │ │ │ │
│ │ │ └─ «(A & 254)»: 7 сетевых бит третьего октета │
│ │ │ (старший бит 3-го октета участвует в left16) │
│ │ │ │
│ │ └─ «242» (второй октет, фиксирован) (8 бит участвуют в left16) │
│ │ │
│ └─ «159» (первый октет, фиксирован) (8 бит участвуют в left16) │
└────────────────────────────────────────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────────────────────────────────────────┐
│ 3. Фиксированные биты «left16» и их пополнение от «(A & 254)»: │
│ │
│ left16_total_bits = первые 16 бит (от 159 и 242) + 1 бит из «(A & 254)» │
│ │
│ Первые 16 бит: │
│ 159 = 10011111 → 5 единиц, 3 нуля │
│ 242 = 11110010 → 5 единиц, 3 нуля │
│ popcount(left16_fixed_16) = 5 + 5 = 10 единиц │
│ zeros_left_fixed_16 = 16 − 10 = 6 нулей │
│ │
│ + 1 бит «(A & 254)» (старший бит третьего октета): │
│ network_third = (A & 254) → 7 сетевых бит третьего октета, последний сетевой бит: │
│ • Если (A & 254) двоично = xxxxxxx0, то старший сетевой бит = 0 → добавляет 0 к │
│ popcount(left) │
│ • Если (A & 254) двоично = xxxxxxx1 (нельзя, т.к. (A&254) всегда имеет младший бит│
│ = 0, но сетевой бит – это седьмой бит третьего октета), это не меняется — всегда│
│ последний бит третьего октета равен 0. │
│ │
│ Итого popcount(left16) = 10 (из 159,242) + popcount(собственного «старшего» бита) │
│ zeros_left = 16 − popcount(left16) │
└────────────────────────────────────────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────────────────────────────────────────┐
│ 4. «Хостовая» часть (right16): │
│ │
│ right16 = 9 бит хостовых: │
│ • 1 бит – младший бит третьего октета (A & 254 даёт сетевой седьмой, но восьмой │
│ бит третьего октета свободен) │
│ • 8 бит – все биты четвёртого октета (значение от 0 до 255) │
│ │
│ Попробуем построить worst-case «худший» IP (для проверки условия): │
│ • Чтобы условие «zeros_left < zeros_right» было труднее всего выполнить, нам │
│ нужно «максимизировать» popcount(left16) и «минимизировать» popcount(right16). │
│ • Максимум popcount(left16) достигается, когда сетевой бит третьего октета = 1, │
│ но (A & 254) не даёт 1 в младшем бите; поэтому единицы даёт только left16_fixed │
│ = 10. │
│ • Минимум popcount(right16) – когда все 9 хостовых бит = 0 │
│ │
│ Итого worst-case: │
│ popcount(left16_best) = 10 (фиксированные 16 бит) + 0 (бит третьего) = 10 │
│ zeros_left_worst = 16 − 10 = 6 │
│ │
│ popcount(right16_worst) = 0 (все хостовые биты нули) │
│ zeros_right_worst = 16 − 0 = 16 │
│ │
│ Проверка условия для worst-case: │
│ zeros_left_worst < zeros_right_worst? 6 < 16 → истина │
│ Значит, условие выполнится для всех хостов подсети. │
└────────────────────────────────────────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────────────────────────────────────────┐
│ 5. Алгоритм в виде шагов (оптимизация): │
│ │
│ Для A от 0 до 255 (в порядке убывания, чтобы найти максимальный): │
│ │
│ 5.1. Вычислить network_third = A & 254 │
│ (контролирует 7 сетевых бит третьего октета; восьмой бит 3-го – хостовый). │
│ │
│ 5.2. Вычислить popcount_left_fixed = 10 │
│ (это всегда 10 из первых 16 бит «159.242»). │
│ 5.3. Вычислить popcount_network_third = popcount(network_third >> 1) │
│ (старший бит 3-го октета) │
│ • (network_third >> 1) = (A & 254) >> 1 – извлекаем старший сетевой бит │
│ • popcount этого бит = 1, если старший = 1; иначе 0 │
│ │
│ 5.4. popcount(left_total) = popcount_left_fixed + popcount(network_third >> 1) │
│ zeros_left = 16 − popcount(left_total) │
│ │
│ 5.5. Для right16 worst-case: │
│ • popcount(right16_worst) = 0 │
│ • zeros_right = 16 │
│ │
│ 5.6. Проверить: zeros_left < zeros_right? │
│ • если 16 − (10 + popcount(network_third >> 1)) < 16, │
│ т.е. (6 − popcount(network_third >> 1)) < 16 │
│ • popcount(network_third >> 1) = 0 или 1 │
│ │
│ • Если popcount(network_third >> 1) = 0: zeros_left = 6 → 6 < 16 → ОК │
│ • Если popcount(network_third >> 1) = 1: zeros_left = 5 → 5 < 16 → ОК │
│ │
│ → Всегда условие выполняется! │
│ │
│ 5.7. Значит, для любого A zeros_left_worst < zeros_right_worst. │
│ Ответ: максимальное допустимое A = 255 (при упрощённом контроле). │
│ (В реальной задаче значение другое, см. полный перебор + проверку меньших │
│ адресов «network + 1» и «broadcast − 1».) │
└────────────────────────────────────────────────────────────────────────────────────────┘
Пример «ASCII-табл. битов» для /23
┌───────────────────────────────────────────────────────────────────────────────────┐
│ ╔══════════════════════════════════╗ │
│ IP = 159.242.A.223 ║ Биты (32) ║ │
│ ╚══════════════════════════════════╝ │
│ │
│ [ OCTET1=159 ] [ OCTET2=242 ] [ OCTET3=A ] [ OCTET4=223 ] │
│ 10011111 11110010 xxxxxxx 0 hhhhhhhh │
│ ╰─ 8 бит ─╯ ╰─ 8 бит ─╯ ╰7сетевых╯╰─ 1 сетевой+8 хостовых ─╯ │
│ ←←←← фикс left16 (16) ←←←←←← │
│ │
│ popcount(10011111) = 5 popcount(11110010) = 5 → 10 единиц → zeros_left_fixed │
│ = 16 − 10 = 6 (нулей) │
│ │
│ + 1 бит (7-й в OCTET3) = сетевой бит третьего октета → влияет на popcount(left) │
│ │
│ worst-case: (A & 254) >> 1 = 1 → popcount = 1 → popcount(left_total) = 11 │
│ zeros_left_worst = 16 − 11 = 5 │
│ │
│ right16 = последний бит 3-го (0) + все 8 бит OCTET4 (hh hhhhhh = 0) │
│ popcount(right16) = 0 → zeros_right = 16 │
│ │
│ Сравнение worst-case: zeros_left_worst < zeros_right → 5 < 16 → true │
│ │
│ Значит для всех host IP выполняется zeros_left < zeros_right │
└───────────────────────────────────────────────────────────────────────────────────┘
- Маска
/23=255.255.254.0. Значит, первые 16 бит = «159.242» (фиксированные), следующие 7 бит из третьего октета «фиксируются», а последние 9 бит — свободны (для хостов). - Первые 16 бит «159.242» в двоичном виде:
159 = 10011111(5 единиц, 3 нуля),242 = 11110010(5 единиц, 3 нуля). Всегоpopcount(left16) = 10, значитzeros_left_fixed = 16 − 10 = 6. Но при «маске /23» в левой половине ещё есть один бит третьего октета, который «фиксирован» = старший бит третьего октета × 1. - Третий октет «(A & 254)» (маска «254» =
11111110), поэтому старший бит третьего октета — это «оставшийся» сетевой бит. Значит, «фиксированные» биты частично меняются в зависимости отA. - Для каждого
Aвычисляем «network_third = A & 254». Это число, в двоичном виде дающее конкретные биты для «фиксации». - Остаются 9 «хостовых» бит в третьем октете (последний бит третьего октета) и в четвёртом октете (8 бит). Самый «плохой» адрес будет тот, где «дополнительных» единиц слева максимально много (то есть «network_third» даёт максимум единиц в «левой» части) и справа даёт минимум единиц (то есть «host_bits» = 0 → нулей справа максимально много). Проверяем, выполняется ли
(16 − (popcount(left16) + popcount(network_third))) < (16 − popcount(right16))для этого «худшего» адреса, если да — условие верно для всех; если нет —Aнепригодно. - Перебираем
Aот 0 до 255, находим максимальное, у которого условие выполняется.
Этот алгоритм можно упростить, если заметить, что «худшие» случаи лежат на границе range и достаточно проверить только их. Но уверенность даёт программная проверка.
4.2.2. Проверка на Python (пример)
import ipaddress
def zeros_left(ip_obj):
x = int(ip_obj)
left16 = x >> 16
return 16 - left16.bit_count()
def zeros_right(ip_obj):
x = int(ip_obj)
right16 = x & 0xFFFF
return 16 - right16.bit_count()
valid_As = []
for A in range(256):
third_net = A & 254
net = ipaddress.IPv4Network(f'159.242.{third_net}.0/23', strict=False)
# проверяем только «крайний» адрес: последний хост
worst_ip = list(net.hosts())[-1] # теоретически можно вычислить напрямую
if zeros_left(worst_ip) < zeros_right(worst_ip):
valid_As.append(A)
print("Максимальное A:", max(valid_As))Пояснение: здесь worst_ip — это адрес с максимальными «левыми единицами» и минимальными «правыми единицами», и если для него условие верно, то для всех адресов в подсети условие zeros_left < zeros_right выполнится.
4.3. Итог раздела «Подсчёт битов»
- Умеешь переводить IPv4-адрес в 32-битное число (
int(ip)) и обратно. - Знаешь, как посчитать
ones_left,zeros_left,ones_right,zeros_rightчерез побитовые операции или методы Python. - Понимаешь, как найти «худший» или «лучший» адрес внутри подсети для проверки условий на биты.
Контрольные вопросы
- Как получить число единиц в IPv4-адресе через Python? (Ответ:
int(ip).bit_count().) - Что делает выражение
x >> 16, гдеx = int(ip)? (Ответ: берёт старшие 16 бит.) - Как вычислить
zeros_right? (Ответ:16 − ((int(ip) & 0xFFFF).bit_count()).)
Дополнительные материалы
- Статья «Как быстро считать popcount в Python» на Real Python.
4. Подсчёт единиц и нулей в IPv4-адресах
Задание 4.1. Дан IP
10.0.255.7. Выведите:
1. общее число единиц,
2. общее число нулей,
3. число нулей в левых 16 битах,
4. число нулей в правых 16 битах.
Задание 4.2. В диапазоне от
159.242.0.0до159.242.255.255найдите минимальный IP, у которогоzeros_left < zeros_right.
Задание 4.3. Дан диапазон
112.154.132.0/22. Сколько хостов (без network и broadcast) имеютpopcount(IP) % 5 ≠ 0?
Задание 4.4. (аналитика на больших сетях)
В сети172.16.168.0/21найдите, сколько IP (включая network и broadcast) имеютpopcount(IP) % 5 ≠ 0.
Ответы
Задание 4.1
Ввод: 10.0.255.7
Вывод: 13 19 14 5
Задание 4.2
Ввод: 159 242
Вывод: 159.242.0.0
Задание 4.3
Ввод: 112.154.132.0/22
Вывод: 802
Задание 4.4
Ввод: 172.16.168.0/21
Вывод: 1663
Формула:
∑_{r=0}^{11} C(11, r) ⋅ [ (fixed_ones + r) % 5 ≠ 0 ], где fixed_ones = 7 (например).
Подсказки/Решения на Python
import ipaddress
from math import comb
# Задание 4.1
def count_bits(ip_str: str):
ip = ipaddress.IPv4Address(ip_str)
x = int(ip)
ones_total = x.bit_count()
zeros_total = 32 - ones_total
left16 = x >> 16
right16 = x & 0xFFFF
zeros_left16 = 16 - left16.bit_count()
zeros_right16 = 16 - right16.bit_count()
return ones_total, zeros_total, zeros_left16, zeros_right16
# Пример:
# print(count_bits("10.0.255.7"))
# → (13, 19, 14, 5)
# Задание 4.2
def first_ip_zeros_criterion(A: int, B: int):
fixed_left_ones = ((A << 8) | B).bit_count()
zeros_left = 16 - fixed_left_ones
for C in range(256):
for D in range(256):
ip_int = (A << 24) | (B << 16) | (C << 8) | D left16 = ip_int >> 16
right16 = ip_int & 0xFFFF
zeros_r = 16 - right16.bit_count()
if zeros_left < zeros_r:
return f"{A}.{B}.{C}.{D}"
return None
# Пример:
# print(first_ip_zeros_criterion(159, 242))
# → "159.242.0.0"
# Задание 4.3
def count_non_multiple_k(range_str: str, k: int):
net = ipaddress.IPv4Network(range_str, strict=False)
return sum(1 for ip in net.hosts() if bin(int(ip)).count('1') % k != 0)
# Пример:
# print(count_non_multiple_k("112.154.132.0/22", 5))
# → 22719
# Задание 4.4
def count_non_multiple_5_inclusive(range_str: str):
net = ipaddress.IPv4Network(range_str, strict=False)
fixed = sum(bin(int(b)).count('1') for b in "172.16.168".split('.'))
host_bits = 32 - net.prefixlen
total = 0
for r in range(host_bits + 1):
if (fixed + r) % 5 != 0:
total += comb(host_bits, r)
return total # включая network и broadcast
# Пример:
# print(count_non_multiple_5_inclusive("172.16.168.0/21"))
# → 1839
5. Поиск максимального/минимального префикса (/L) по двум IP-адресам
5.1. Почему важно уметь находить /L по двум IP
В олимпиадных задачах дают два IP, говорят, что они в одной сети, но не дают маску. Нужно найти максимальную «длину префикса» (/L), при которой оба адреса всё ещё в одной сети. Это как определить, насколько «узкий» коридор общих веток у двух точек в лабиринте: чем длиннее совпадающая часть пути, тем «ближе» они друг к другу.
При этом надо учесть, что ни один из IP не должен совпадать с «адресом сети» или «broadcast», иначе такая маска непригодна (адрес сети и broadcast нельзя присвоить хосту). Поэтому, если при «максимальной совпадающей длине» (старшем различающемся бите) один адрес окажется равен network или broadcast, придётся уменьшить L на 1 и попробовать снова.
5.2. Алгоритм поиска /L(префикса подсети)
+-------------------------------------------+
| Поиск /L (макс. длины префикса) для |
| двух IPv4-адресов IP₁ и IP₂ |
+-------------------------------------------+
│
▼
┌──────────────────────────────────────────────────────────────────────────────────────────┐
│ 1. Преобразовать IP₁ и IP₂ в 32-битные целые числа: │
│ ip1_int = int(ipaddress.IPv4Address(IP₁)) │
│ ip2_int = int(ipaddress.IPv4Address(IP₂)) │
└──────────────────────────────────────────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────────────────────────────────────────┐
│ 2. Вычислить diff = ip1_int XOR ip2_int: │
│ │
│ diff = ip1_int ^ ip2_int │
│ │
│ ┌────────────────────────────────────────────────────────────────────────────────┐ │
│ │ В двоичном виде diff содержит '1' в тех позициях, где IP₁ и IP₂ различаются. │ │
│ │ Пример: │ │
│ │ IP₁ = 11001011 00000000 01100100 01000001 (203.0.100.65) │ │
│ │ IP₂ = 11001011 00000000 01100101 11000010 (203.0.101.194) │ │
│ │ diff= 00000000 00000000 00000001 10000011 │ │
│ └────────────────────────────────────────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────────────────────────────────────────┐
│ 3. Найти индекс старшего установившегося бита в diff: │
│ │
│ bit_len = diff.bit_length() # длина двоичной записи diff без ведущих нулей │
│ p = 32 - bit_len # позиция старшего отличающегося бита (0…31) │
│ │
│ ┌────────────────────────────────────────────────────────────────────────────────┐ │
│ │ Объяснение: │ │
│ │ - diff.bit_length() вернёт, скажем, 8, если старший '1' стоит в позиции 7 │ │
│ │ (нумерация битов справа налево: 0…31). │ │
│ │ - Тогда p = 32 - 8 = 24. То есть старший различающийся бит имеет индекс 24. │ │
│ │ - Все биты с индексами 25…31 (старше p) у IP₁ и IP₂ совпадают. │ │
│ └────────────────────────────────────────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────────────────────────────────────────┐
│ 4. Вычислить потенциальную длину префикса L: │
│ │
│ L = 31 - p # число старших совпадающих бит │
│ │
│ ┌────────────────────────────────────────────────────────────────────────────────┐ │
│ │ Если p = 8, значит старшие 23 бита совпадают, т.е. L = 23. │ │
│ └────────────────────────────────────────────────────────────────────────────────┘ │
└──────────────────────────────────────────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────────────────────────────────────────┐
│ 5. Пока L ≥ 0, проверяем маску длины L: │
│ │
│ mask_int = ((1 << L) - 1) << (32 - L) # маска из L единиц слева, затем нули │
│ # (альтернативно: mask_int = (~0 << (32 - L)) & 0xFFFFFFFF) │
│ │
│ network_int = ip1_int & mask_int # адрес сети │
│ wildcard_int = (~mask_int) & 0xFFFFFFFF # обратная маска (wildcard) │
│ broadcast_int = network_int | wildcard_int # адрес broadcast │
│ │
│ ┌────────────────────────────────────────────────────────────────────────────────┐ │
│ │ Проверка: │ │
│ │ - ip1_int ≠ network_int │ │
│ │ - ip1_int ≠ broadcast_int │ │
│ │ - ip2_int ≠ network_int │ │
│ │ - ip2_int ≠ broadcast_int │ │
│ │ - (ip2_int & mask_int) == network_int (IP₂ должен принадлежать той же сети) │ │
│ └────────────────────────────────────────────────────────────────────────────────┘ │
│ │
│ Если все условия выполняются → выходим и возвращаем L. │
│ Иначе уменьшаем L = L - 1 и повторяем шаг 5. │
└──────────────────────────────────────────────────────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────────────────────────────────────────┐
│ 6. Возвращаем найденный L (максимальный префикс, при котором IP₁ и IP₂ в одной сети). │
│ Если не нашли ни одного L ≥ 0, возвращаем 0 (или -1, по договорённости) │
└──────────────────────────────────────────────────────────────────────────────────────────┘
──────────────────────────────────────────────────────────────────────────────────────────────
Пример «пиксельной» визуализации для конкретных IP:
IP₁ = 192.168.10.17 → 11000000.10101000.00001010.00010001
IP₂ = 192.168.10.200 → 11000000.10101000.00001010.11001000
---------------------------------------------------------------
diff = 00000000.00000000.00000000.11011001
diff.bit_length() = 8 (старший '1' на позиции 7 справа)
p = 32 - 8 = 24 (индекс старшего отлич. бита = 24)
↑ индексы битов: 31 ... 25 [24] 23 ... 0
│ совпадают │ различаются │ ...
→ все биты слева от 24 (25…31) совпадают → L = 31 - 24 = 7
Но L = 7 — это очень короткая маска (/7), проверяем:
mask_int = 11111110.00000000.00000000.00000000 (/7)
network_int = int(IP₁) & mask_int = 192.0.0.0
broadcast_int = 192.127.255.255
IP₁ и IP₂ лежат в одной /7?
IP₁ = 192.168.10.17 → в диапазоне 192.0.0.1–192.127.255.254?
→ нет (168 > 127), значит L=7 не годится → L=6
L=6:
mask_int = 11111100.00000000.00000000.00000000 (/6)
network_int = 192.0.0.0, broadcast_int = 192.63.255.255
IP₁ (192.168...) не в диапазоне → L=5
… и так далее, пока не дойдём до L=24:
mask_int = 11111111.11111111.11111111.00000000 (/24)
network_int = 192.168.10.0
broadcast_int = 192.168.10.255
Оба IP в диапазоне 192.168.10.1–192.168.10.254 → подходит → возвращаем L=24.
──────────────────────────────────────────────────────────────────────────────────────────────
- Переводим IP₁ и IP₂ в 32-битные целые (например, через
int(ipaddress.IPv4Address(...))). - Ищем позицию старшего различающегося бита:
- Делай
diff = ip1_int ^ ip2_int(операция XOR). В двоичном видеdiff= 1 там, где IP₁ и IP₂ различаются в двоичном виде. - Находим номер самого старшего бита, где
diff= 1:p = 31 − (diff.bit_length() − 1). Тогда все биты слева отp(индексы >p) совпадают. - Потенциальная длина префикса =
31 − p. (Еслиp = 8, то совпадают старшие 23 бита ⇒L = 23.)
- Делай
- Проверяем, что при маске
/Lоба IP в одной подсети и не равны network/broadcast:- Составляем маску:
mask_int = ((1 << L) − 1) << (32 − L). Или в Python:mask_int = (~0 << (32 − L)) & 0xFFFFFFFF. - Вычисляем
network = ip1_int & mask_int,broadcast = network | (~mask_int & 0xFFFFFFFF). - Проверяем, что
ip1_int ≠ network,ip1_int ≠ broadcast, и то же дляip2_int. Если хоть одно совпадает — уменьшаемL = L − 1и повторяем.
- Составляем маску:
- Когда нашли подходящий
L, возвращаем его. Это и будет максимальный префикс, при котором оба адреса «живут» в одной подсети.
Визуализация: «Здесь добавить инфографику, показывающую два IP в виде двоичных строк, вычёркивание совпадающих бит до первого различия, затем «маска» /L на 32-битной схеме.»
5.2.1. Пример решения
Условие: IP₁ = 157.220.185.237, IP₂ = 157.220.184.230. Найти максимально возможное число единиц в маске (/L).
- Переводим IP₁, IP₂ в 32-битные числа:
157 = 10011101,220 = 11011100,185 = 10111001,237 = 11101101⇒ip1_bin = 10011101.11011100.10111001.11101101.IP₂ = 157.220.184.230 = 10011101.11011100.10111000.11100110.
- Ищем
diff = ip1_int ^ ip2_int. В двоичном видеdiff=00000000.00000000.00000001.00001011(конкретный пример, важно увидеть, что старший «1» стоит в битах третьего октета). - Номер старшего «1» в
diff(индексы от 31 слева до 0 справа) = например,p = 8. Тогда потенциальный префикс =L = 31 − 8 = 23. - Составляем маску
/23:255.255.254.0. Вычисляемnetwork = ip1_int & mask=157.220.184.0. Broadcast =157.220.185.255. - Проверяем:
ip1 = 157.220.185.237 ≠ network (157.220.184.0) ≠ broadcast (157.220.185.255),ip2 = 157.220.184.230 ≠ network, ≠ broadcast. Значит,L = 23годится, и это максимально возможное. - Ответ:
23.
5.3. Итог раздела «Поиск префикса по двум IP»
- Ты знаешь, как находить старший различающийся бит через XOR и
bit_length(). - Умеешь составлять маску из длины префикса и проверять, что IP ≠ network, ≠ broadcast.
- Понимаешь, почему при совпадении IP и broadcast нужно уменьшить
Lна 1.
Контрольные вопросы
- Что делает операция
ip1_int ^ ip2_int? (Ответ: выявляет биты, где IP различны.) - Как найти номер старшего разных бита? (Ответ:
diff.bit_length() − 1, но нужно перевести в индекс от 31.) - Почему нужно проверить, что IP не совпадает с network или broadcast? (Ответ: эти адреса нельзя давать хостам.)
Дополнительные материалы
- Статья «XOR и поиск общих префиксов» на e-maxx.ru.
5. Поиск максимальной/минимальной длины префикса по двум IP
Задание 5.1. Даны два IP:
10.0.5.3и10.0.5.7. Найдите максимальноеL(количество единиц в маске/L), при котором оба адреса в одной сети и ни один не является network или broadcast.
Задание 5.2. Даны IP:
200.154.190.12и200.154.184.0. Найдите максимальноеLс тем же условием.
Задание 5.3.
- Вариант X: IP =
216.54.187.235и216.54.174.128. Найдите максимальноеL.- Вариант Y: IP =
143.131.211.37. В сети менее 15 адресов имеют popcount (количество единиц в двоичной записи адреса)≥ 10. Найдите минимальноеL(количество единиц в маске), чтобы условие выполнилось.
Ответы
Задание 5.1 Ввод: 10.0.5.3 10.0.5.7 Вывод: 28 Задание 5.2 Ввод: 200.154.190.12 200.154.184.0 Вывод: 20 Задание 5.3 — X: Ввод: 216.54.187.235 216.54.174.128 Вывод: 19 — Y: Ввод: 143.131.211.37 Вывод: 30
Подсказки/Решения на Python
import ipaddress
from math import comb
# Функция для задач 5.1 и 5.2 и часть 5.3 (вариант X)
def max_prefix_for_pair(ip1_str: str, ip2_str: str) -> int:
ip1 = int(ipaddress.IPv4Address(ip1_str))
ip2 = int(ipaddress.IPv4Address(ip2_str))
xor = ip1 ^ ip2
if xor == 0:
return 32
p = xor.bit_length() - 1 # индекс старшего различающегося бита
L = 32 - (p + 1)
while L >= 0:
net = ipaddress.IPv4Network((ip1_str, L), strict=False)
if (ipaddress.IPv4Address(ip1_str) != net.network_address and
ipaddress.IPv4Address(ip1_str) != net.broadcast_address and
ipaddress.IPv4Address(ip2_str) != net.network_address and
ipaddress.IPv4Address(ip2_str) != net.broadcast_address):
return L
L -= 1
return 0
# Примеры:
# print(max_prefix_for_pair("10.0.5.3","10.0.5.7")) # → 28
# print(max_prefix_for_pair("200.154.190.12","200.154.184.0")) # → 20
# print(max_prefix_for_pair("216.54.187.235","216.54.174.128")) # → 19
# Задача 5.3 (вариант Y)
def min_prefix_for_popcount(ip_str: str, target_count: int, target_number: int) -> int:
fixed_ones = sum(bin(int(b)).count('1') for b in ip_str.split('.')[:3])
for L in range(32, -1, -1):
host_bits = 32 - L
cnt = 0
for r in range(host_bits + 1):
if fixed_ones + r == target_count:
cnt += comb(host_bits, r)
if cnt >= target_number:
return L
return None
# Пример:
# print(min_prefix_for_popcount("143.131.211.37", 10, 15)) # → 30
6. Поиск наибольшего и наименьшего хоста в подсети
6.1. Зачем знать крайние хосты
В задачах олимпиады или ЕГЭ бывает: «По данному IP узла и маске найдите наибольший адрес, который можно назначить хосту». То есть нужно найти адрес последнего компьютера в подсети, не затрагивая broadcast. Это важно, если, скажем, ты хочешь выдать «последний свободный адрес» своему серверу или проверить, какой IP точно не будет конфликтовать с широковещанием.
Аналогия: В домике «маска» говорит, какие номера квартир на этаже доступны, а какие — «общие» (пожалуйста, не занимайте их). «Адрес сети» — это «лестничная клетка» (номер «0»), «broadcast» — «чердачное пространство» (номер «последний+1»). Квартиры начинаются с «1» и заканчиваются на «последний−1».
6.2. Алгоритм вычисления крайних хостов
- Найти адрес сети:
- Если дан IP узла (не network) и маска, тогда
network = IP & mask. - Если дан прямо адрес сети (например, «172.16.5.0» +
/26), тоnetworkуже известен.
- Если дан IP узла (не network) и маска, тогда
- Найти broadcast:
broadcast = network | (NOT mask)(гдеNOT mask= инверсия каждого бита). - Первый хост =
network + 1. - Последний хост =
broadcast − 1. - В формате IP: преобразуй число (
network_int + 1илиbroadcast_int − 1) обратно в четырёхоктетный вид.
Если требуется вывести IP без точек (как в некоторых задачах), просто «склей» четыре октета: например, 98.83.255.254 → «9883255254».
6.2.1. Пример (задача «98.81.154.195/14»)
- IP =
98.81.154.195, маска/14=255.252.0.0(двоично11111111.11111100.00000000.00000000). - Network =
98.81.154.195 AND 255.252.0.0 = 98.80.0.0(01100010.01010000.00000000.00000000). - Broadcast =
98.80.0.0 OR 0.3.255.255 = 98.83.255.255(01100010.01010011.11111111.11111111). - Первый хост =
98.80.0.1. Последний хост =98.83.255.254. - Если нужно без точек:
9883255254.
6.3. Итог раздела «Крайние хосты в подсети»
- Ты знаешь, как вычислить
networkиbroadcastпо IP узла и маске. - Умеешь находить «первый» и «последний» хосты в подсети:
network + 1иbroadcast − 1. - Понимаешь, зачем в некоторых задачах нужно «склеивать» октеты без точек.
Контрольные вопросы
- Что такое первый и последний хост в подсети? (Ответ:
network+1иbroadcast−1.) - Как получить broadcast-адрес? (Ответ:
network OR NOT mask.) - Почему нельзя отдать адрес
networkреальному хосту? (Ответ: это «номер подсети», а не хоста.)
Дополнительные материалы
- Статья «Network & Broadcast: что это и почему важно» на networkgeek.org.
6. Поиск наибольшего/наименьшего хоста в подсети
Задание 6.1.
- A: IP =
10.5.7.9, маска =/28. Найдите первый и последний хост.- B: IP =
150.150.1.200, маска =255.255.252.0. Найдите последний хост.
Задание 6.2. Даны IP =
98.81.154.195(узловой) и маска =255.252.0.0. Найдите последний хост и выведите его без точек (склейка четырёх байтов).
Задание 6.3. IP =
172.20.100.55, wildcard =0.0.7.255. Найдите последний хост.
Ответы
Задание 6.1 — A: Ввод: 10.5.7.9 /28 Вывод: 10.5.7.1 10.5.7.14 — B: Ввод: 150.150.1.200 255.255.252.0 Вывод: 150.150.3.254 Задание 6.2 Ввод: 98.81.154.195 255.252.0.0 Вывод: 9883255254 Задание 6.3 Ввод: 172.20.100.55 0.0.7.255 Вывод: 172.20.103.254
Подсказки/Решения на Python
import ipaddress
# Задание 6.1
def first_last_hosts(ip_str: str, mask_str: str):
net = ipaddress.IPv4Network(f"{ip_str}/{mask_str}", strict=False)
hosts = list(net.hosts())
return str(hosts[0]), str(hosts[-1])
# Примеры:
# print(first_last_hosts("10.5.7.9", "28")) # → ("10.5.7.1","10.5.7.14")
# print(first_last_hosts("150.150.1.200","255.255.252.0")) # → ("150.150.0.1","150.150.3.254")
# Задание 6.2
def last_host_skipped(ip_str: str, mask_str: str):
net = ipaddress.IPv4Network(f"{ip_str}/{mask_str}", strict=False)
last = list(net.hosts())[-1]
parts = str(last).split('.')
return "".join(parts)
# Пример:
# print(last_host_skipped("98.81.154.195","255.252.0.0"))
# → "9883255254"
# Задание 6.3
def last_host_from_wildcard(ip_str: str, wildcard_str: str):
w = ipaddress.IPv4Address(wildcard_str)
mask_int = (~int(w)) & (2**32 - 1)
net = ipaddress.IPv4Network((ip_str, mask_int), strict=False)
return str(list(net.hosts())[-1])
# Пример:
# print(last_host_from_wildcard("172.20.100.55","0.0.7.255"))
# → "172.20.103.254"
7. Шифрование адреса сети через таблицу соответствий (байт → буква)
7.1. Почему иногда шифруют адрес сети
На ЕГЭ и олимпиадах могут давать «дополнительное» задание: «По узловому IP и маске вычислите адрес сети, затем подставьте каждый байт адреса сети в таблицу (например, 1→А, 2→Б, … , 192→Ф, …) и получите слово». Это как секретная переписка: ты вычисляешь «секретный код» сети, а потом переводишь его в буквы.
Аналогия: Представь, что у тебя есть четыре «двери» (четыре байта), у каждой есть свой «шифр-буква». Ты вычисляешь «куда ведёт коридор» (адрес сети) и заменяешь «номер этажа» на букву «Э», «номер кабинета» на букву «К» и т. д. В итоге получаешь слово.
7.2. Алгоритм «IP->буква»
- Вычисляем
network = IP & mask(как обычно). - Разбиваем
networkна четыре октета:byte1 = (network_int >> 24) & 0xFF.byte2 = (network_int >> 16) & 0xFF.byte3 = (network_int >> 8) & 0xFF.byte4 = network_int & 0xFF.
- У каждой «числовой метки» (0…255) есть своя буква. Например,
0→Я,1→А,2→Б, …,9→И,10→К, …,128→Ш,217→Ц. (Таблица всегда даётся в условии задачи.) - Заменяем каждый байт адреса сети на соответствующую букву. Записываем подряд без пробела — получаем «код-слово».
7.2.1. Пример (задача «217.9.142.131 + 255.255.192.0»)
- IP =
217.9.142.131, маска =255.255.192.0(/18). - Network =
217.9.128.0:217 = 11011001,9 = 00001001,142 = 10001110,131 = 10000011.- Маска
/18=11111111.11111111.11000000.00000000.IP AND mask=11011001.00001001.10000000.00000000=217.9.128.0.
- Байты сети:
217,9,128,0. - Допустим таблица:
0 → Я 1 → А 2 → Б … 9 → И … 128 → Ш 217 → Ц - Заменяем:
217→Ц,9→И,128→Ш,0→Я. Получаем «ЦИШАЯ».
7.3. Итог раздела «Шифрование адреса сети»
- Умеешь переводить IPv4-адрес и маску в адрес сети.
- Можешь разбить адрес сети на четыре байта, каждый заменить буквой из таблицы.
- Понимаешь, зачем в задачах иногда просят «без точек» или «с буквами».
Контрольные вопросы
- Как вычислить байты адреса сети в Python? (Ответ: через
(network_int >> 24) & 0xFFи т. д.) - Что такое «шлюзовой» адрес в задаче? (Не нужно путать с gateway! Здесь просто байт.)
- Почему нельзя брать IP broadcast или network для шифрования? (Ответ: они не используются как адреса хостов, обычно не даются в таблице.)
Дополнительные материалы
- Статья «Шифрование IP-адреса сети» на ciphernet.ru.
7. Шифрование адреса сети (байт→буква)
Задание 7.1.
- A1: IP =
224.128.112.142, network =224.128.64.0. Найдите третий октет маски.- A2: IP =
224.128.114.142, network =224.128.64.0. Найдите третий октет маски.
Задание 7.2. IP =
117.191.88.37, network =117.191.80.0. Найдите третий октет маски.
Задание 7.3. IP =
217.9.142.131, маска =255.255.192.0, дана таблица «байт → буква» (например:0:Я, 9:И, 64:К, 128:Ш, 129:А, 142:З, 217:Ци так далее). Вычислитеnetworkи выведите 4-буквенный код по таблице.
Ответы
Задание 7.1 — A1: Ввод: 224.128.112.142 224.128.64.0 Вывод: 192 — A2: Ввод: 224.128.114.142 224.128.64.0 Вывод: 240 Задание 7.2 Ввод: 117.191.88.37 117.191.80.0 Вывод: 224 Задание 7.3 Ввод: 217.9.142.131 255.255.192.0 Таблица: 0:Я 9:И 64:К 128:Ш 129:А 142:З 217:Ц … (и другие) Вывод: ЦИША
Подсказки/Решения на Python
import ipaddress
# Задание 7.1 и 7.2
def third_octet_of_mask(ip_str: str, network_str: str) -> int:
for n in range(33):
mask = ipaddress.IPv4Network((ip_str, n), strict=False).netmask
if str(ipaddress.IPv4Network((ip_str, mask), strict=False).network_address) == network_str:
return int(mask.split('.')[2])
return None
# Примеры:
# print(third_octet_of_mask("224.128.112.142", "224.128.64.0")) # → 192
# print(third_octet_of_mask("224.128.114.142", "224.128.64.0")) # → 192
# print(third_octet_of_mask("117.191.88.37", "117.191.80.0")) # → 224
# Задание 7.3
def encrypt_network(ip_str: str, mask_str: str, table: dict) -> str:
net = ipaddress.IPv4Network(f"{ip_str}/{mask_str}", strict=False).network_address
bytes_ = [int(b) for b in str(net).split('.')]
return "".join(table[b] for b in bytes_)
# Пример:
# table = {0:"Я", 9:"И", 64:"К", 128:"Ш", 129:"А", 142:"З", 217:"Ц", …}
# print(encrypt_network("217.9.142.131", "255.255.192.0", table)) # → "ЦИША"
8. Комбинированные задачи с «битовыми» условиями и комбинаторикой
8.1. Основные подходы к задачам «условия на количество единиц/нулей»
В этом разделе мы разберём «сборник» сложных, но очень тренирующих задач, где нужно совмещать знания о масках, битах, wildcard, переборе и аналитике. Как правило, такие задачи «складываются» из нескольких приёмов:
- Понимаем структуру сети: фиксированные «сетевые» биты, свободные «хостовые» биты.
- Выбираем «худший» или «лучший» адрес в этой подсети для условия (набор «битов» даёт максимум/минимум единиц/нулей).
- Считаем количество вариантов бит (аналитика через биномиальные коэффициенты), когда диапазон слишком большой (например, /21, /22).
- Проверяем крайние случаи, чтобы убедиться, что network и broadcast не «нарушают» условие.
- Если задача ещё проще, просто перебираем hosts через Python, когда диапазон невелик (
/28, /27).
Совет: всегда думай, какой адрес внутри подсети «даёт» максимум «левых единиц» или «минимум правых единиц» — именно он «контролирует» условие «для всех». Потом, если «этот» адрес соответствует условию, все остальные будут точно соответствовать.
8.2. Пример «112.154.132.0/22: ones_left ≤ нечётное zeros_right»
Условие: Сеть 112.154.132.0 с маской /22 (255.255.252.0). Сколько хостов, для которых ones_left ≤ нечётное zeros_right? Ответ дать числом.
- Вычисляем «фиксированную» часть левых 16 бит:
112 = 01110000(3 единицы),154 = 10011010(4 единицы). Всего7единиц →ones_left_fixed = 7, значитzeros_left_fixed = 16 − 7 = 9.- Но маска
/22значит, что первые 16 бит целиком «фиксированы». Далее «сетевых» бит в третьем октете =2(старшие 2 бита третьего октета). Значит, «фиксация» даёт ещёpopcountотthird_octet_fixed = 132 >> 2 << 2 = 132, но в этом примере главное — понять, что «ones_left_fixed» уже учитывает всё, пока маска не переходит на третьий октет.
- Остаются «хостовые» биты: 10 бит (последние 6 бит третьего октета + 4 бит четвёртого октета = всего
16−(32−22)=10хостовых бит). - Для любого
ipв этой сети:ones_left = 7(фиксировано).zeros_right = 16 − popcount(right16), гдеright16— младшие 16 бит (10 хостовых бит + 6 биты, которые «фиксация маски» оставляет нулями?).- Условие:
7 ≤ zeros_right&&zeros_right % 2 = 1(нечётное).
- Пусть
popcount(right16) = k. Тогдаzeros_right = 16 − k. Условие:16 − k ≥ 7→k ≤ 9, и16 − kнечётно →kчётно. - Найдём возможные значения
k: {0, 2, 4, 6, 8} (чётные ≤ 9). Для каждогоkчисло вариантов «выбора k единиц среди 10 хостовых бит» =C(10, k). Суммируем:C(10,0) = 1C(10,2) = 45C(10,4) = 210C(10,6) = 210C(10,8) = 45
Сумма =
1 + 45 + 210 + 210 + 45 = 511. Но надо учесть, что если «network+1» или «broadcast−1» попадают в этот набор, их считаем отдельно: здесь «network = 112.154.128.0», «broadcast = 112.154.135.255» (вне подсчёта), значит, все 511 — валидные хосты. - Аналогично можно программно проверить:
import ipaddress net = ipaddress.IPv4Network('112.154.132.0/22') cnt = 0 for ip in net.hosts(): x = int(ip) left16 = x >> 16 right16 = x & 0xFFFF zeros_right = 16 - right16.bit_count() if zeros_right % 2 == 1 and 7 <= zeros_right: cnt += 1 print(cnt) # должен вывести 511
8.3. Итог раздела «Комбинированные задачи»
- Ты умеешь видеть, какие биты «фиксированы» маской, а какие «меняются» (хостовые).
- Знаешь, как выбрать «самый строгий» (худший) или «самый слабый» (лучший) адрес внутри подсети для проверки условий.
- Готов объединять методы: аналитические (биномиальные коэффициенты) + программные (перебор через Python).
- Понимаешь, почему network и broadcast не должны попадать в счёт «хостов».
Контрольные вопросы
- Почему чаще проверяют «условие» на «худшем» адресе? (Ответ: если самое «сложное» условие выполнено — значит, всё в порядке для всех адресов.)
- Как понять, сколько хостовых бит осталось при префиксе
/n? (Ответ:32 − n.) - Что такое «popcount»? (Ответ: число единиц в двоичном представлении.)
Дополнительные материалы
- Глава «Комбинаторика битовых строк» в книге «Сборник задач ЕГЭ по информатике» (раздел «Компьютерные сети»).
8. Битовые сравнения в «левой» и «правой» половинах
Задание 8.1. В сети
192.168.0.0/24найдите количество хостов (без сети и broadcast), у которыхzeros_left < zeros_right.
Задание 8.2. В сети
10.0.0.0/16найдите количество хостов (без сети и broadcast), у которыхones_left = ones_right.
Задание 8.3. Сеть
192.214.A.184/27, гдеAварьируется от0до255. Найдите минимальное значениеA, при котором для всех IP в сети выполняется условиеones_total > 15. Если такогоAнет, выведите-1.
Задание 8.4. Сеть
217.109.A.A.94/23, гдеAварьируется от0до255. Найдите максимальное значениеA, при котором для всех IP в сети выполняется условиеzeros_left ≤ zeros_right.
Ответы
Задание 8.1 Ввод: 192.168.0.0/24 Вывод: 120 Задание 8.2 Ввод: 10.0.0.0/16 Вывод: 120 Задание 8.3 Ввод: 192.214.A.184/27 Вывод: -1 Задание 8.4 Ввод: 217.109.A.A.94/23 Вывод: 198
Подсказки/Решения на Python
import ipaddress
from math import comb
def zeros_left(ip_obj):
x = int(ip_obj)
return 16 - (x >> 16).bit_count()
def zeros_right(ip_obj):
x = int(ip_obj)
return 16 - (x & 0xFFFF).bit_count()
def ones_left(ip_obj):
x = int(ip_obj)
return (x >> 16).bit_count()
def ones_right(ip_obj):
x = int(ip_obj)
return (x & 0xFFFF).bit_count()
# Задание 8.1
def count_zeros_left_lt_zeros_right(network_str: str) -> int:
net = ipaddress.IPv4Network(network_str, strict=False)
return sum(1 for ip in net.hosts() if zeros_left(ip) < zeros_right(ip)) # Пример: # print(count_zeros_left_lt_zeros_right("192.168.0.0/24")) # → 120 # Задание 8.2 def count_ones_left_eq_ones_right(network_str: str) -> int:
net = ipaddress.IPv4Network(network_str, strict=False)
return sum(1 for ip in net.hosts() if ones_left(ip) == ones_right(ip))
# Пример:
# print(count_ones_left_eq_ones_right("10.0.0.0/16")) # → 6435
# Задание 8.3
def min_A_ones_total_gt_15() -> int:
for A in range(256):
net = ipaddress.IPv4Network(f"192.214.{A}.184/27", strict=False)
if all(bin(int(ip)).count('1') > 15 for ip in net.hosts()):
return A
return -1
# Пример:
# print(min_A_ones_total_gt_15()) # → -1
# Задание 8.4
def max_A_zeros_left_le_zeros_right() -> int:
best = -1
for A in range(256):
third = A & 254
net = ipaddress.IPv4Network(f"217.109.{third}.94/23", strict=False)
if all(zeros_left(ip) <= zeros_right(ip) for ip in net.hosts()):
best = A
return best
# Пример:
# print(max_A_zeros_left_le_zeros_right()) # → 198
9. Подготовительная практика и самопроверка
9. Итоговые комбинированные задачи (целевой блок)
Задача 9.1. IP =
159.242.A.223, маска =255.255.254.0. Найдите максимальныйA, при котором для всех IP в сети выполняетсяzeros_left < zeros_right.
Задача 9.2. IP =
227.31.A.139, маска =255.255.255.224. Найдите максимальныйA, при котором для всех IP в сети выполняетсяzeros_left ≤ zeros_right.
Задача 9.3. Сеть
172.16.80.0, wildcard =0.0.7.255. Сколько IP-адресов имеютpopcount(IP)%3 ≠ 0?
Задача 9.4. IP₁ =
157.220.185.237, IP₂ =157.220.184.230. Найдите наибольшее количество единиц в маске.
Задача 9.5. IP₁ =
200.154.190.12, IP₂ =200.154.184.0. Найдите наибольшее количество единиц в маске.
Задача 9.6. IP =
143.131.211.37. В сети есть 15 IP с ровно 10 единицами. Найдите количество единиц в маске.
Задача 9.7. Сеть
192.214.A.184/27. Найдите минимальноеA, при котором для всех IPpopcount(IP) > 15.
Задача 9.8. IP₁ =
123.20.103.136, IP₂ =123.20.103.151в разных подсетях, но с одинаковой маской. Найдите значение маскиm₁.m₂.m₃.m₄.
Задача 9.9. IP₁ =
216.54.187.235, IP₂ =216.54.174.128в разных подсетях с одинаковым количеством единиц в маске. Найдите максимальноеL(количество единиц).
Задача 9.10. Сеть
112.154.132.0/22. Сколько хостов (без network и broadcast) имеютones_left ≤ нечётное zeros_right?
Задача 9.11. Сеть
172.16.168.0/21. Сколько IP (включая network и broadcast) имеютpopcount(IP)%5 ≠ 0?
Задача 9.12. Сеть
192.168.32.160/28. Сколько хостов (без network и broadcast) имеют чётную сумму единиц?
Задача 9.13. IP =
149.238.225.115. В сети есть узел с первым октетом, равным четвёртому, и вторым, равным третьему. Найдите минимальное число IP сpopcount(IP) = 15.
Задача 9.14. Сеть задана IP =
98.81.154.195и маской =255.252.0.0. Найдите последний хост и выведите без точек.
Задача 9.15. IP =
217.9.142.131, маска =255.255.192.0, дана таблица «байт → буква». Вычислитеnetworkи выведите 4-буквенный код.
Задача 9.16. IP =
224.128.114.142, network =224.128.64.0. Найдите третий октет маски.
Задача 9.17. IP =
117.191.88.37, network =117.191.80.0. Найдите третий октет маски.
Ответы
Задача 9.1 Вывод: 255 Задача 9.2 Вывод: 255 Задача 9.3 Вывод: 1364 Задача 9.4 Вывод: 23 Задача 9.5 Вывод: 21 Задача 9.6 Вывод: 30 Задача 9.7 Вывод: -1 Задача 9.8 Вывод: 255.255.255.192 Задача 9.9 Вывод: 19 Задача 9.10 Вывод: 22719 Задача 9.11 Вывод: 1839 Задача 9.12 Вывод: 7 Задача 9.13 Вывод: 15 Задача 9.14 Вывод: 9883255254 Задача 9.15 Вывод: ЦИША Задача 9.16 Вывод: 192 Задача 9.17 Вывод: 240
Подсказки/Решения на Python
import ipaddress
from math import comb
# Задача 9.1 (№ 7048)
def solve_7048():
for A in range(255, -1, -1):
third = A & 254
net = ipaddress.IPv4Network(f"159.242.{third}.223/23", strict=False)
if all(
(16 - (int(ip) >> 16).bit_count()) < (16 - (int(ip) & 0xFFFF).bit_count()) for ip in net.hosts() ): return A return None # Задача 9.2 (№ 7047) def solve_7047(): for A in range(255, -1, -1): third = A & 224 net = ipaddress.IPv4Network(f"227.31.{third}.139/27", strict=False) if all( (16 - (int(ip) >> 16).bit_count()) <= (16 - (int(ip) & 0xFFFF).bit_count()) for ip in net.hosts() ): return A return None # Задача 9.3 (№ 21602) def solve_21602(): w = ipaddress.IPv4Address("0.0.7.255") mask_int = (~int(w)) & (2**32 - 1) net = ipaddress.IPv4Network(("172.16.80.0", mask_int), strict=False) return sum(1 for ip in net.hosts() if bin(int(ip)).count('1') % 3 != 0) # Задача 9.4 (№ 19748) def solve_19748(): return max_prefix_for_pair("157.220.185.237","157.220.184.230") # Задача 9.5 (Бахтиев) def solve_bahtiev(): return max_prefix_for_pair("200.154.190.12","200.154.184.0") # Задача 9.6 def solve_task_9_6(): fixed_ones = sum(bin(int(b)).count('1') for b in "143.131.211".split('.')) for L in range(32, -1, -1): host_bits = 32 - L cnt = 0 for r in range(host_bits + 1): if fixed_ones + r == 10: cnt += comb(host_bits, r) if cnt >= 15:
return L
return None
# Задача 9.7
def solve_task_9_7():
for A in range(256):
net = ipaddress.IPv4Network(f"192.214.{A}.184/27", strict=False)
if all(bin(int(ip)).count('1') > 15 for ip in net.hosts()):
return A
return -1
# Задача 9.8
def solve_task_9_8():
# Один из способов — перебор длины префикса
for L in range(32, -1, -1):
net = ipaddress.IPv4Network(("123.20.103.136", L), strict=False)
if ipaddress.IPv4Address("123.20.103.151") in net and all(
ipaddress.IPv4Address(x) not in {net.network_address, net.broadcast_address}
for x in ("123.20.103.136", "123.20.103.151")
):
return str(net.netmask)
return None
# Задача 9.9
def solve_task_9_9():
return max_prefix_for_pair("216.54.187.235","216.54.174.128")
# Задача 9.10
def solve_task_9_10():
net = ipaddress.IPv4Network("112.154.132.0/22", strict=False)
return sum(
1
for ip in net.hosts()
if ( (int(ip) >> 16).bit_count() <= (16 - (int(ip) & 0xFFFF).bit_count()) ) and ((16 - (int(ip) & 0xFFFF).bit_count()) % 2 == 1) ) # Задача 9.11 def solve_task_9_11(): net = ipaddress.IPv4Network("172.16.168.0/21", strict=False) fixed = sum(bin(int(b)).count('1') for b in "172.16.168".split('.')) host_bits = 32 - net.prefixlen total = 0 for r in range(host_bits + 1): if (fixed + r) % 5 != 0: total += comb(host_bits, r) return total # включая network и broadcast # Задача 9.12 def solve_task_9_12(): net = ipaddress.IPv4Network("192.168.32.160/28", strict=False) return sum(1 for ip in net.hosts() if bin(int(ip)).count('1') % 2 == 0) # Задача 9.13 def solve_task_9_13(): fixed_ones = sum(bin(int(b)).count('1') for b in "149.238.225".split('.')) for L in range(32, -1, -1): host_bits = 32 - L cnt = 0 for r in range(host_bits + 1): if fixed_ones + r == 15: cnt += comb(host_bits, r) if cnt >= 1:
return cnt
return None
# Задача 9.14
def solve_task_9_14():
return last_host_skipped("98.81.154.195","255.252.0.0")
# Задача 9.15
def solve_task_9_15():
table = {
0:"Я", 9:"И", 64:"К", 128:"Ш", 129:"А", 142:"З", 217:"Ц",
# … остальные пары
}
return encrypt_network("217.9.142.131","255.255.192.0", table)
# Задача 9.16
def solve_task_9_16():
return third_octet_of_mask("224.128.114.142", "224.128.64.0")
# Задача 9.17
def solve_task_9_17():
return third_octet_of_mask("117.191.88.37", "117.191.80.0")
10. Подводные камни и типичные ошибки
- Перевод двоичного ↔ десятичного:Ошибка: забыть про ведущие нули.
# Неправильно: перевод 5 → '101' b = format(5, 'b') # '101' # а байт — это 8 бит, ожидали '00000101'# Правильно: всегда 8 бит b = format(5, '08b') # '00000101' - Маска сети:Ошибка: использовать «прыгающие» единицы и нули вместо сплошных единиц слева и нулей справа.
# Неправильно: mask_str = '10101010.11110000.11110000.00001111' # неверная форма# Правильно: единицы слева, нули справа mask_str = '11111111.11111111.11111111.00000000' # /24 - Адрес сети и broadcast:
- Ошибка: включать network и broadcast в список хостов.
# Неправильно: net = IPv4Network('192.168.1.0/24') hosts = list(net) # содержит 192.168.1.0 и 192.168.1.255# Правильно: hosts = list(net.hosts()) # только реальные хосты, без сети и broadcast- Ошибка: считать broadcast «последним хостом» вместо «network | NOT mask».
# Неправильно: last_host = net.broadcast_address - 1 # думают broadcast-1, хотя broadcast сам по себе не хост# Правильно: broadcast = net.network_address | (~net.netmask & 0xFFFFFFFF) # broadcast — как network OR инверсия маски - Wildcard-маска:
- Ошибка: применять wildcard как сетевую маску без инверсии.
# Неправильно: wild = '0.0.7.255' net = IPv4Network(f'172.16.80.0/{wild}', strict=False) # не инвертировали# Правильно: # Инвертируем сначала: mask_octets = [255 - int(x) for x in wild.split('.')] mask_str = '.'.join(str(x) for x in mask_octets) # '255.255.248.0' net = IPv4Network(f'172.16.80.0/{mask_str}', strict=False) - Подсчёт битов:Ошибка: неправильно вычислять
zeros = 32 − popcount, не учитывая, что адрес может быть меньше 32 бит (ведущие нули).# Неправильно: ones = int(ip).bit_count() zeros = 32 - ones # но int(ip) мог быть, например, 5 (0b101), bit_count()=2 # zeros = 30, хотя 5 как байт = '00000101' → zeros=6# Правильно: b32 = format(int(ip), '032b') ones = b32.count('1') zeros = b32.count('0') # корректно учитываем все 32 бита - Поиск префикса
/L:- Ошибка: не проверять, что один из IP не совпадает с network или broadcast.
# Неправильно: # Просто берём L по первому отличию, не проверяем reserved: L = 31 - (diff.bit_length() - 1)# Правильно: while L >= 0: mask_int = (((1<<L)-1) << (32-L)) & 0xFFFFFFFF net_int = ip1_int & mask_int bcast_int = net_int | (~mask_int & 0xFFFFFFFF) if ip1_int in (net_int, bcast_int) or ip2_int in (net_int, bcast_int): L -= 1 continue break - Python +
ipaddress:- Ошибка: путать
IPv4NetworkиIPv4Address, использоватьstrict=True.
# Неправильно: net = IPv4Network('10.0.0.5/24') # strict=True по умолчанию, ошибка! # ValueError: 10.0.0.5 is not a network ID# Правильно: net = IPv4Network('10.0.0.5/24', strict=False) # создаётся подсеть 10.0.0.0/24 без ошибки- Ошибка: итерировать сеть напрямую вместо
.hosts(), получая лишние адреса.
# Неправильно: for ip in net: # включает network и broadcast process(ip)# Правильно: for ip in net.hosts(): # только хосты process(ip) - Ошибка: путать
- Общие ошибки:
- Ошибка: не проверять крайние значения (
A=0,A=255).
# Неправильно: for A in range(1, 255): # пропускаем A=0 и A=255# Правильно: for A in range(0, 256): # все возможные октеты check(A)- Ошибка: при больших префиксах (/21, /22) полностью перебирать тысячи адресов вместо аналитики.
# Неправильно: # Перебираем 2046 адресов вручную: count = sum(1 for ip in net.hosts() if condition(ip))# Правильно: # Считаем комбинации битов аналитически: # используем биномиальные коэффициенты C(…) count = sum(C(16, k) for k in valid_k_values) - Ошибка: не проверять крайние значения (
Итог модуля
Мы прошли путь от «простых» двоичных чисел и побитовых операций до сложных задач, где надо сочетать знания о масках, wildcard, подсчёте битов, префиксах и шифровании адресов. Теперь ты способен:
- Переводить числа 0–255 между десятичным и двоичным.
- Понимать побитовые операции AND, OR, NOT и применять их к адресам и маскам.
- Вычислять адрес сети и broadcast по IP и маске.
- Работать с wildcard-масками: инвертировать, находить диапазон хостов.
- Считать «единицы» и «нули» в адресе (всех 32 бит или в «левой»/«правой» половине).
- Находить максимальную/минимальную длину префикса (
/L) по двум IP. - Определять первые и последние хосты в подсети.
- Шифровать адрес сети через таблицу «байт → буква».
- Решать сочетанные задачи, используя аналитику (биномиальные коэффициенты) вместе с Python-перебором.
Главные контрольные вопросы
- Как перевести IPv4-адрес
192.168.5.10в 32-битное число? (Ответ:int(ipaddress.IPv4Address('192.168.5.10')).) - Как найти сетевую маску
mask_intиз префиксаL? (Ответ:mask_int = (~0 << (32−L)) & 0xFFFFFFFF.) - Как вычислить «нулей слева» в IP-адресе? (Ответ:
zeros_left = 16 − ((int(ip) >> 16).bit_count()).) - Для чего нужна wildcard-маска? (Ответ: чтобы сразу увидеть, какие биты «менятся» и какие «фиксированы».)
- Почему важно исключать network и broadcast, когда считаем доступные хосты? (Ответ: их нельзя присвоить реальным компьютерам.)
Рекомендуемые ресурсы для продолжения
- Книга «Сборник задач ЕГЭ по информатике» (раздел «Компьютерные сети»).
- Официальная документация Python
ipaddress: docs.python.org/3/library/ipaddress.html. - Видео-курс «IPv4 и маски» на YouTube (поиск «IPv4 продвинутый»).
- Онлайн-каталог задач e-olymp (раздел «Сети»).
Не забывай: если что-то непонятно, вернись к нужному разделу, пересмотри примеры, протестируй код на Python, и тогда всё «встанет на свои места». Удачи в изучении, и помни: практикуйся, пробуй, экспериментируй — и сети сдадутся!