Вывод обратного определения подсети

IP-подсеть определяется двумя частями: сетью и длиной префикса или маской.
Например, 192.168.0.0/16 (или 192.168.0.0/255.255.0.0).

Считается, что такой IP-адрес, как 192.168.1.1, соответствует этой подсети, потому что

(192.168.1.1 & 255.255.0.0) == 192.168.0.0

Меня интересует то, что можно назвать инверсией подсети
, которая описывается следующим образом:

Для данной SubnetA (скажем, NetworkA / MaskA),
обратным SubnetA является список из k подсетей, таких что

Если IP-адрес A соответствует SubnetA,
A не будет соответствовать ни одной из этих k подсетей, и
Каждый IP-адрес B, который не соответствует SubnetA,
будет точно соответствовать 1 из этих k подсети.

Код не нужен, меня интересует правильный и оптимальный способ.

У меня есть оптимизированный ответ, указанный для справки ниже, поэтому он не отвлекает людей, пытающихся решить эту проблему. Сохранили принятие ответа Рафала, поскольку он тоже первым понял это.


subnet ip-address algorithm
person nik    schedule 03.07.2009    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Одна подсеть для каждого немаскированного бита b в A, совпадающая со всеми предыдущими битами в A, отличающаяся b, маскирующая все последующие биты. Таким образом, каждый адрес i, не входящий в A, будет соответствовать только одной из вышеуказанных сетей, а именно той, которая отвечает за первый бит i, не совпадающий с A.

person Rafał Dowgird    schedule 03.07.2009

arrow_upward
0
arrow_downward

Хм. Я бы сказал, что это практически любая подсеть, кроме A, с той же маской...

person Lucero    schedule 03.07.2009
comment
Вы перечислили 192.168.0.0/16? - person nik; 03.07.2009

arrow_upward
0
arrow_downward

Если вы представляете себе дерево всех подсетей, начинающееся с 0.0.0.0/32 и разветвляющееся в каждом бите, вам нужны все ветви, которые не ведут в вашу подсеть. Вы поднимаетесь на один шаг (бит), обнуляете этот бит и добавляете родственного узла (имеет другой бит в соответствующем месте) этого узла в свой набор. (Это то же самое, что говорит Рафал, только выражено по-другому.) Вы можете сделать это так (рабочий код С#):

using System;
using System.Text;

namespace so_subnet_complement
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter subnet in the 192.168.0.0/16 format.");
            string[] line = Console.ReadLine().Split('/');
            string[] segments = line[0].Split('.');
            uint ip = 0;
            uint multiplier = 1;
            for (int i = 3; i >= 0; i--)
            {
                ip += byte.Parse(segments[i]) * multiplier;
                multiplier *= 0x100;
            }
            int mask = int.Parse(line[1]);

            Console.WriteLine("Complement subnets:");
            writeComplementSubnets(ip, mask);
        }

        static void writeComplementSubnets(uint ip, int mask)
        {
            for (;mask < 32; mask++)
            {
                uint newIp =(uint)(ip & (0xFFFFFFFF << mask) ^ (1 << mask));
                Console.WriteLine("{0}/{1}", ipToString(newIp), mask);
            }
        }

        static string ipToString(uint ip)
        {
            StringBuilder result = new StringBuilder(15);
            uint mask = 0xFF000000;
            int shift = 24;
            for (int i = 0; i < 4; i++)
            {
                result.Append((ip & mask) >> shift);
                mask >>= 8;
                shift -= 8;
                if (i < 3)
                    result.Append('.');
            }
            return result.ToString();
        }
    }
}

Наиболее важным является метод writeComplementSubnets. IP-адрес представлен в естественном (для меня) представлении, так что 192.168.0.0 становится 0xC0A80000.

РЕДАКТИРОВАТЬ: я понял, что рекурсия здесь абсолютно не нужна. Кажется, что функциональное программирование иногда вызывает неправильное мышление.

person svick    schedule 03.07.2009

arrow_upward
0
arrow_downward

У меня есть оптимизированный ответ, отмеченный для справки в этом фрагменте кода.

unsigned int network; // 32-bit network. Say (192.168.0.0 or 0xC0A80000)
unsigned int mask; // 32-bit mask (0xFFFF0000 for the example case)

i = 0; // to iterate over the network bits
do {
    bitmask = (unsigned int)(0x80000000 >> i)
    invmask = (unsigned int)(0xFFFFFFFF << (31-i));

    invnet = (invmask & network) ^ bitmask;
    printSubnet(invnet, invmask); // this stores/prints the subnet

} while (mask && i<32); // only while we have valid mask

Принял ответ Рафала, так как он тоже понял это первым.

Вот инверсия для 192.168.0.0/16, чтобы проверить правильность.

[1] 0.0.0.0 / 128.0.0.0         ;    00000000
[2] 128.0.0.0 / 192.0.0.0       ;    80000000
[3] 224.0.0.0 / 224.0.0.0       ;    e0000000
[4] 208.0.0.0 / 240.0.0.0       ;    d0000000
[5] 200.0.0.0 / 248.0.0.0       ;    c8000000
[6] 196.0.0.0 / 252.0.0.0       ;    c4000000
[7] 194.0.0.0 / 254.0.0.0       ;    c2000000
[8] 193.0.0.0 / 255.0.0.0       ;    c1000000
[9] 192.0.0.0 / 255.128.0.0     ;    c0000000
[10] 192.192.0.0 / 255.192.0.0  ;    c0c00000
[11] 192.128.0.0 / 255.224.0.0  ;    c0800000
[12] 192.176.0.0 / 255.240.0.0  ;    c0b00000
[13] 192.160.0.0 / 255.248.0.0  ;    c0a00000
[14] 192.172.0.0 / 255.252.0.0  ;    c0ac0000
[15] 192.170.0.0 / 255.254.0.0  ;    c0aa0000
[16] 192.169.0.0 / 255.255.0.0  ;    c0a90000
person nik    schedule 10.04.2013