java - 在java中将ip数组转换为最小的cidr子网列表

Question

我有一个如下所示的 ip 数组，我想将其转换为最小的 cidr 子网列表。 Java 中有这样的库吗？

例如:

1.1.3.0
1.1.3.1
1.1.3.2
1.1.3.3
..
1.1.3.254
1.1.3.255
1.2.3.0
1.2.3.1
1.2.3.2
1.2.3.3
..
1.2.3.254
1.2.3.255
1.3.3.0
1.3.3.1
1.3.3.2
1.3.3.3
..
1.3.3.128
1.3.3.129

转换为

1.1.3.0/24
1.2.3.0/24
1.3.3.0/25
1.3.3.128/31

提前致谢。

Answer 1

不知道Java中是否有可用的库。确实，我对 Java 知之甚少:)但是我可以给你一个解决问题的算法，如果有帮助的话。

1) 将 ip 地址转换为整数对，其中第一个整数是 ip 地址的二进制表示形式 (a.b.c.d -> a << 24 + b << 16 + c << 8 + d)，第二个整数是 IP 地址的二进制表示形式整数是 32(也就是说，最初每个地址都是它自己的子网 [1])。

2)对列表进行排序。

3) 现在从第二对开始扫描已排序的列表。对于每一对，如果您可以将其与前一对组合，请这样做并继续尝试，直到组合得尽可能长。两对 [base1, bits1]和[base2, bits2]可以组合如果 bits1 == bits2和base2 ^ base1 == 1 << (32 - bits1) 。在这种情况下，组合为 [base1, bits1 - 1] .

4) 最后，将这些对转换回 CIDR 表示法:第一个整数是子网的基数(转换回点分十进制时)，第二个整数是位宽。

第 2 步和第 3 步均为 O(n log n)

脚注 1:在您的示例中，您没有包含最后一个字节为 0 的地址，这意味着我的算法将在您的测试用例中失败。您必须将它们添加到列表中。这一点揭示了 CIDR 子网定义中一个微妙但重要的细节:从技术上讲，最小的可能子网是/30，因为该范围的第一个和最后一个 ip 都被保留。因此/31 将没有有效的 IP 地址。然而，人们经常使用术语 CIDR 子网来表示“识别一组 IP 地址的位掩码”，就像用作过滤器表达式一样。