13.3 Переборные типы — подсчёт адресов по условию

Подсчёт адресов по условию на биты

Это самый частый тип последних лет. Дан адрес и маска. Нужно сосчитать адреса сети, у которых число единиц удовлетворяет условию.

Разберёмся с терминами, их путают чаще всего. Левые два байта — это первые 16 бит. Правые два байта — последние 16 бит.

Ключевое наблюдение: в маленькой сети левая половина зафиксирована сетью. Слева число единиц постоянно. Справа — меняется. Значит перебирать нужно только правую часть.

Способ решения честный один — перебор. Пробегаем все адреса, у каждого считаем единицы слева и справа, сравниваем, копим счётчик.

Worked example

Сеть 142.108.56.118, маска 255.255.255.240. Нулей 4, значит адресов 16: с .112 по .127.

левые 16 бит  = 142.108 -> единиц 4 + 4 = 8   (постоянно!)
правые 16 бит = 56.oct4 -> единиц 3 + (единицы в oct4)

условие: 8 < 3 + единицы(oct4)
         значит единицы(oct4) > 5, то есть 6 и больше

Теперь смотрим последний байт от 112 до 127 и считаем единицы:

112 = 01110000  единиц 3   нет
119 = 01110111  единиц 6   ДА
123 = 01111011  единиц 6   ДА
125 = 01111101  единиц 6   ДА
126 = 01111110  единиц 6   ДА
127 = 01111111  единиц 7   ДА

всего подходит: 5

Ещё примеры

Пример 1. Когда ответ равен нулю. Если слева единиц максимум, обогнать их справа невозможно.

сеть 255.255.0.0 / 255.255.255.240
левые:  255.255 -> единиц 16  (максимум!)
правых больше 16 быть не может  -> ответ 0

Пример 2. Когда подходят все адреса. Если слева нулей много, условие выполняется всегда.

сеть 0.0.255.255 / 255.255.255.240
левые:  0.0 -> единиц 0
справа единиц всегда больше 0 (байты 255.24x)
-> подходят все 16 адресов

Пример 3. Как считать единицы быстро. Держи в голове «полуфабрикаты».

255 = 11111111  -> 8 единиц
240 = 11110000  -> 4
128 = 10000000  -> 1
127 = 01111111  -> 7
  0 = 00000000  -> 0

▶ Try it: для сети 100.200.60.80 с маской 255.255.255.240 перебери 16 адресов и посчитай подходящие.