假设子网按升序排列。我们考虑32位二进制字符串s以及相应子网掩码的长度n。
考虑s的长度为n的前缀。通过将表示此前缀的数字加1,我们可以得到下一个子网中第一个地址的前缀。为了看清楚这一点,想象将前缀右侧的所有内容都填充为1;这是该子网中最大可能的地址,因此下一个地址必须在下一个子网中。对其加1将进行地址分配到子网掩码内部的部分,因此我们可以直接考虑它。
这给我们提供了所需的位串,但它并没有告诉我们相应子网掩码的长度n。显然,n必须至少足够长以包括我们获得的所有非零数字串。否则,可以证明我们会包含当前子网中的地址。然而,我们可能需要更多的0来避免与列表中下一个子网重叠。我们还必须确保保留足够的零,使我们的新子网与列表中的下一个子网至少在一个数字上不同:下一个地址中的最后一个非零数字。
以下是有关您的问题的示例:
192.168.1.24 / 29
192.168.1.40 / 30
192.168.1.64 / 28
我们将把它们读取为:
11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 01000000 / 28
现在,考虑这些中的第一个
11000000 10101000 00000001 00011000 / 29
我们考虑长度为29的前缀:
11000000 10101000 00000001 00011
添加一个:
11000000 10101000 00000001 00100
我们的 n 必须至少为 27。要查看是否需要更长,请考虑我们列表中的下一个子网:
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00100
^
我们的子网与下一个子网在第29位不同,这也是下一个子网中最右边的非零位置。因此,n = 29; 我们创建了一个新的子网:
11000000 10101000 00000001 00100000 / 29
如果我们对刚刚创建的子网应用相同的过程,我们会发现我们生成了与原始列表中下一个子网对应的完全相同的前缀。我们可以检测到这一点,并意识到这意味着这里没有更多的空隙需要填充,然后继续进行。
下一个子网是
11000000 10101000 00000001 00101000 / 30
长度为30的前缀是:
11000000 10101000 00000001 001010
加一:
11000000 10101000 00000001 001011
与下一个子网进行比较:
11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 001011
我们必须至少选择 n = 30,这样我们才能得到子网:
11000000 10101000 00000001 00101100 / 30
考虑长度为30的前缀并加1:
11000000 10101000 00000001 001011
+ 1
=================================
11000000 10101000 00000001 001100
与下一个进行比较:
11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 001100
我们必须至少要有n为28,这样我们才能得到
11000000 10101000 00000001 00110000 / 28
考虑长度为28的子字符串,加1后得到与原列表中下一个子网所属的相同的比特串。我们意识到这意味着我们已经填补了空缺,因此我们继续前进。
我们正在查看原始输入的最后一个,因此没有剩余内容需要填充。完成。我们的子网:
11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00100000 / 29 <<<
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00101100 / 30 <<<
11000000 10101000 00000001 00110000 / 28 <<<
11000000 10101000 00000001 01000000 / 28
请注意,这不会创建超出提供的输入范围的子网范围。如果要这样做,您的算法可以在列表前缀加上最小子网,并在列表后缀加上最大子网。让我们用0.0.0.0/1作为最小子网和255.255.255.255/32作为最大子网来完成最小化操作:
00000000 00000000 00000000 00000000 / 1
0
+1
下一个子网将给我们第一个真正的输入子网。现在的子网如下:
00000000 00000000 00000000 00000000 / 1 <<<
10000000 00000000 00000000 00000000 / 2 <<<
11000000 00000000 00000000 00000000 / 9 <<<
11000000 10000000 00000000 00000000 / 11 <<<
11000000 10100000 00000000 00000000 / 13 <<<
11000000 10101000 00000000 00000000 / 24 <<<
11000000 10101000 00000001 00000000 / 28 <<<
11000000 10101000 00000001 00010000 / 29 <<<
11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00100000 / 29 <<<
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00101100 / 30 <<<
11000000 10101000 00000001 00110000 / 28 <<<
11000000 10101000 00000001 01000000 / 28
我们可以在另一端重复这个练习:
11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 0100
+1
= 11000000 10101000 00000001 0101
11111111 11111111 11111111 11111111
^
=> n = 28 (must include rightmost 1 of s + 1)
=> 11000000 10101000 00000001 01010000 / 28 <<<<<<<
11000000 10101000 00000001 01010000 / 28
11000000 10101000 00000001 0101
+1
= 11000000 10101000 00000001 0110
11111111 11111111 11111111 11111111
^
=> n = 27
=> 11000000 10101000 00000001 01100000 / 27 <<<<<<<
11000000 10101000 00000001 01100000 / 27
11000000 10101000 00000001 011
+1
= 11000000 10101000 00000001 100
11111111 11111111 11111111 11111111
^
=> n = 25
=> 11000000 10101000 00000001 10000000 / 25 <<<<<<<
11000000 10101000 00000001 10000000 / 25
11000000 10101000 00000001 1
+1
= 11000000 10101000 00000010 0
11111111 11111111 11111111 11111111
^
=> n = 23
=> 11000000 10101000 00000010 00000000 / 23 <<<<<<<
不必列出所有术语,因为那会变得单调乏味,我们可以注意到当我们有一串0时,我们将减少n并将最右边的向左移动一个空格。所以,我们可以跳过这部分:
=> 11000000 10101000 00000100 00000000 / 22 <<<<<<<
=> 11000000 10101000 00001000 00000000 / 21 <<<<<<<
=> 11000000 10101000 00010000 00000000 / 20 <<<<<<<
=> 11000000 10101000 00100000 00000000 / 19 <<<<<<<
=> 11000000 10101000 01000000 00000000 / 18 <<<<<<<
=> 11000000 10101000 10000000 00000000 / 17 <<<<<<<
=> 11000000 10101001 00000000 00000000 / 16 <<<<<<<
=> 11000000 10101010 00000000 00000000 / 15 <<<<<<<
=> 11000000 10101100 00000000 00000000 / 14 <<<<<<<
我们注意到当n减少k时,01^k变成了10^k;因此我们再次跳过并添加。
=> 11000000 10110000 00000000 00000000 / 12 <<<<<<<
=> 11000000 11000000 00000000 00000000 / 10 <<<<<<<
=> 11000001 00000000 00000000 00000000 / 8 <<<<<<<
回到第一条规则:
=> 11000010 00000000 00000000 00000000 / 7 <<<<<<<
=> 11000100 00000000 00000000 00000000 / 6 <<<<<<<
=> 11001000 00000000 00000000 00000000 / 5 <<<<<<<
=> 11010000 00000000 00000000 00000000 / 4 <<<<<<<
下一步,我们获取一个与我们范围结尾匹配的子网,因此我们必须包含一个额外的零以使其不同:
=> 11100000 00000000 00000000 00000000 / 4 <<<<<<<
如果我们真的关心255.255.255.255子网,正确的方法是通过增加n和每次增加1个1的数量来继续扩展它,以获得大约27个更多的子网。然而,如果我们只想填补空缺,我们可以认识到我们目前的情况并添加:
=> 11110000 00000000 00000000 00000000 / 4 <<<<<<<<
这包括了剩余的范围,包括255.255.255.255,因此它本身并不是增强问题的解决方案,但它确实解决了填补空缺的原始问题。我们的完整列表如下:
00000000 00000000 00000000 00000000 / 1 <<<
10000000 00000000 00000000 00000000 / 2 <<<
11000000 00000000 00000000 00000000 / 9 <<<
11000000 10000000 00000000 00000000 / 11 <<<
11000000 10100000 00000000 00000000 / 13 <<<
11000000 10101000 00000000 00000000 / 24 <<<
11000000 10101000 00000001 00000000 / 28 <<<
11000000 10101000 00000001 00010000 / 29 <<<
11000000 10101000 00000001 00011000 / 29
11000000 10101000 00000001 00100000 / 29 <<<
11000000 10101000 00000001 00101000 / 30
11000000 10101000 00000001 00101100 / 30 <<<
11000000 10101000 00000001 00110000 / 28 <<<
11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 01010000 / 28 <<<
11000000 10101000 00000001 01100000 / 27 <<<
11000000 10101000 00000001 10000000 / 25 <<<
11000000 10101000 00000010 00000000 / 23 <<<
11000000 10101000 00000100 00000000 / 22 <<<
11000000 10101000 00001000 00000000 / 21 <<<
11000000 10101000 00010000 00000000 / 20 <<<
11000000 10101000 00100000 00000000 / 19 <<<
11000000 10101000 01000000 00000000 / 18 <<<
11000000 10101000 10000000 00000000 / 17 <<<
11000000 10101001 00000000 00000000 / 16 <<<
11000000 10101010 00000000 00000000 / 15 <<<
11000000 10101100 00000000 00000000 / 14 <<<
11000000 10110000 00000000 00000000 / 12 <<<
11000000 11000000 00000000 00000000 / 10 <<<
11000001 00000000 00000000 00000000 / 8 <<<
11000010 00000000 00000000 00000000 / 7 <<<
11000100 00000000 00000000 00000000 / 6 <<<
11001000 00000000 00000000 00000000 / 5 <<<
11010000 00000000 00000000 00000000 / 4 <<<
11100000 00000000 00000000 00000000 / 3 <<<
与上述解释的两个/4子网不同,我在此列表中放置了一个单独的/3子网,因为它是等效的。