13.3 Переборные типы — чётность числа единиц

Чётность единиц: ровно половина

Даны два узла одной сети. Просят наименьшее возможное число адресов с чётным числом единиц.

Слово «наименьшее» — это команда. Бери самую тесную сеть: самую длинную маску, при которой оба узла ещё вместе. Граница — до первого различающегося бита.

А дальше красивый факт, который экономит всё время. В любой сети адресов с чётным числом единиц ровно половина. Хостовых бит H — значит адресов 2^H, а чётных 2^H−1.

Почему так? Возьми самый младший хостовый бит. Меняешь его — чётность переворачивается. Адреса разбиваются на пары «чётный + нечётный». Пар ровно половина от всех адресов.

Worked example

Узлы 193.45.192.104 и 193.45.206.210. Различие в третьем байте: 192 и 206.

192 = 11000000
206 = 11001110
      \__/ ^ расхождение на 4-м бите байта

совпало всего 16 + 4 = 20 бит  -> тесная сеть /20
хостовых бит H = 32 - 20 = 12

всего адресов: 2^12 = 4096
чётных:        2^11 = 2048   (ровно половина)

Ответ: 2048. Перебирать 4096 адресов не нужно.

Ещё примеры

Пример 1. Проверим правило на крошечной сети. H = 2, всего 4 адреса. Посчитаем единицы вручную.

адрес ...00000100  единиц 1   нечёт
адрес ...00000101  единиц 2   ЧЁТ
адрес ...00000110  единиц 2   ЧЁТ
адрес ...00000111  единиц 3   нечёт

чётных 2 = 4 / 2 = 2^(2-1)   правило работает

Пример 2. Готовая табличка.

H     адресов 2^H    чётных 2^(H-1)
 4         16              8
 8        256            128
10       1024            512
12       4096           2048

Пример 3. Почему «наименьшее» = тесная сеть. Чем длиннее маска, тем меньше адресов, значит меньше и половина.

/20 -> H=12 -> чётных 2048
/18 -> H=14 -> чётных 8192   (сеть шире, чётных больше)
просят наименьшее -> берём самую тесную -> /20

▶ Try it: в сети с H = 10 сколько адресов с чётным числом единиц? Сверься с табличкой.