导出子网定义的逆

Question

IP 子网由两部分定义：网络和前缀长度或掩码。
例如192.168.0.0/16（或192.168.0.0/255.255.0.0）。

像 192.168.1.1 这样的 IP 地址据说与此子网匹配，因为

(192.168.1.1 & 255.255.0.0) == 192.168.0.0

我对所谓的子网的逆子网感兴趣
是这样描述的，

对于给定的子网A（例如，NetworkA / MaskA），
SubnetA 的逆是 k 个子网的列表，例如，

如果 IP 地址 A 与 SubnetA 匹配，
A 不会匹配任何 k 个子网，并且
每个与 SubnetA 不匹配的 IP 地址 B，
将完全匹配这些 k 个子网中的 1 个。

代码不是必需的，我对正确且最佳的方法感兴趣。

---

我在下面注明了供参考的优化答案，因此它不会分散人们尝试将此问题视为问题的注意力。 仍然接受拉法尔的答案，因为他也首先得到了正确的答案。

Answer 1

A 中每个未屏蔽位 b 对应一个子网，与 A 中所有之前的位匹配，与 b 不同，屏蔽所有以下位。 这样，不在 A 中的每个地址 i 将仅匹配上述网络中的一个，即负责 i 的第一位的网络与A不匹配。

Answer 2

嗯。 我想说它基本上是除 A 之外具有相同掩码的任何子网......

Answer 3

如果您想象所有子网的树从 0.0.0.0/32 开始，每一位都有分支，那么您需要所有不通向您的子网的分支。 您向上一步（位），将该位清空，并将该节点的同级（在适当位置具有不同的位）添加到您的集合中。 （与 Rafał 所说的相同，只是表达方式不同。）您可以这样做（工作 C# 代码）：

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。

编辑：我意识到递归在这里绝对是不必要的。 看来函数式编程有时会导致错误的思维。

Answer 4

我在此代码片段中注明了可供参考的优化答案。

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