algorithm - 如何计算IP子网之间的差距？-6ren

algorithm - 如何计算IP子网之间的差距？

转载作者：塔克拉玛干更新时间：2023-11-03 03:23:08

计算输入IP子网之间所有间隔的最有效算法是什么？
示例输入

192.168.1.24 / 29
192.168.1.40 / 30
192.168.1.64 / 28

示例输出

192.168.1.0 / 28   <--- auto-created
192.168.1.16 / 29  <--- auto-created
192.168.1.24 / 29  <--- INPUT
192.168.1.32 / 29  <--- auto-created
192.168.1.40 / 30  <--- INPUT
192.168.1.44 / 30  <--- auto-created
192.168.1.48 / 28  <--- auto-created
192.168.1.64 / 28  <--- INPUT
192.168.1.80 / 28  <--- auto-created
192.168.1.96 / 27  <--- auto-created
192.168.1.128 / 25 <--- auto-created

迄今为止的研究：
第一步对于输入对：192.168.1.0/28、192.168.1.24/29
让我们计算IP子网的数值表示之间的差异：

diff = 3232235800 - 3232235776 = 24

然后以2为基数计算对数：

log2 = log2(24) = 4.58

然后我们可以计算cidr和子网的长度：

cidr = 32 - 4 = 28
ipStart = 3232235776 
ipEnd = 3232235776 + 2^4 - 1 = 3232235776 + 15 = 3232235791

因此，我们添加到列表中：

192.168.1.0/28

但仍有差距，因此：

diff = 3232235800 - 3232235792 = 8
log2 = log2(8) = 3
cidr = 32-3=29
ipStart = 3232235792
ipEnd = 3232235799

所以我们加上第二个：

192.168.1.16/29

等等。但是，有没有一种更有效的方法来发现间隙并生成子网？

最佳答案

假设子网按升序列出。我们考虑32位二进制字符串s以及相应子网掩码的长度n。
考虑长度为n的s的前缀。通过将这个前缀表示的数字加1，我们得到下一个子网中第一个地址的前缀。要看到这一点，想象一下用1s填充前缀右侧的所有内容；这是s的子网中可能的最大地址，因此下一个地址必须在下一个子网中。再加上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位的下一个子网不同，第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的前缀并添加一个：

11000000 10101000 00000001 001011
+                               1
=================================
11000000 10101000 00000001 001100

与下一个比较：

11000000 10101000 00000001 01000000 / 28
11000000 10101000 00000001 001100

我们必须至少有28个，所以我们得到

11000000 10101000 00000001 00110000 / 28

考虑长度为28的子串，添加一个，我们得到的位字符串与属于原始列表中下一个子网的位字符串相同。我们认识到这意味着我们已经填补了空白，所以我们继续前进。
我们正在查看原始输入的最后一个，因此没有任何内容可以填充。完成。我们的子网：

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作为最小子网AD255.255.255.255/32作为最大子网：

00000000 00000000 00000000 00000000 / 1
0
+1
=1
 11000000 10101000 00000001 00011000 / 29
  ^
 => n = 2
 => 10000000 00000000 00000000 00000000 / 2    <<<<<<<<<

10000000 00000000 00000000 00000000 / 2
10
+1
=11
 11000000 10101000 00000001 00011000 / 29
          ^
=> n = 9
=> 11000000 00000000 00000000 00000000 / 9    <<<<<<<<<

11000000 00000000 00000000 00000000 / 9
11000000 0
+1
= 11000000 1
  11000000 10101000 00000001 00011000 / 29
             ^
=> n = 11
=> 11000000 10000000 00000000 00000000 / 11    <<<<<<<<<

11000000 10000000 00000000 00000000 / 11
11000000 100
+1
= 11000000 101
  11000000 10101000 00000001 00011000 / 29
               ^
=> n = 13
=> 11000000 10100000 00000000 00000000 / 13    <<<<<<<<<

11000000 10100000 00000000 00000000 / 13
11000000 10100
+1
= 11000000 10101
  11000000 10101000 00000001 00011000 / 29
                           ^
=> n = 24
=> 11000000 10101000 00000000 00000000 / 24    <<<<<<<<<

11000000 10101000 00000000 00000000 / 24
11000000 10101000 00000000
+1
= 11000000 10101000 00000001
  11000000 10101000 00000001 00011000 / 29
                                ^
=> n = 28
=> 11000000 10101000 00000001 00000000 / 28    <<<<<<<<<

11000000 10101000 00000001 00000000 / 28
11000000 10101000 00000001 0000
+1
= 11000000 10101000 00000001 0001
  11000000 10101000 00000001 00011000 / 29
                                 ^
=> n = 29
=> 11000000 10101000 00000001 00010000 / 29    <<<<<<<<<

下一个将给我们第一个真正的输入子网。子网现在是：

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减少1，并将最右边的左移一个空格。所以，我们跳到前面：

=> 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    <<<<<<<

我们注意到01^k变为10^k，n减少k；因此我们再次跳过添加

=> 11000000 10110000 00000000 00000000 / 12    <<<<<<<
=> 11000000 11000000 00000000 00000000 / 10    <<<<<<<
=> 11000001 00000000 00000000 00000000 / 8     <<<<<<<

回到规则1：

=> 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和1s的数量来继续这个过程，得到大约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子网，因为它是等价的。

关于algorithm - 如何计算IP子网之间的差距？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47390426/

文章推荐： algorithm - 一个关于时间复杂度定义的谜题

文章推荐： java - 将变量声明为最终的内部方法会提高性能吗？

文章推荐： java - 如何递归引用泛型参数？

文章推荐： c# - 用霍纳方案简化算法

java - 如果姓氏的第一个字符在 A 和 M 之间，如何返回 1；如果姓氏的第一个字符在 N 到 Z 之间，如何返回 2？
我需要修复 getLineNumberFor 方法，以便如果 lastName 的第一个字符位于 A 和 M 之间，则返回 1；如果它位于 N 和 Z 之间，则返回 2。在我看来听起来很简单，但我不
javascript - 在 Javascript 中，Onclick Img 标记和递增(在 1-10 之间)和 onclick 其他 img 和递减(在 1-10 之间)相同的计数器
您好，感谢您的帮助!我有这个: 0 我必须在每次点击后增加“pinli
javascript - 切换案例到/之间
Javascript 中是否有一种方法可以在不使用 if 语句的情况下通过 switch case 结构将一个整数与另一个整数进行比较？例如。 switch(integer) { case
delphi - cxgrid列过滤器选项“之间”
我有一列是“日期”类型的。如何在自定义选项中使用“之间”选项？最佳答案请注意，您有2个盒子。 between（在SQL中）包含所有内容，因此将框1设置为：DATE >= startdate，将框2
SQL Server 之间
我有一个表，其中包含年、月和一些数字列 Year Month Total 2011 10 100 2011 11 150 2011 12 100 20
Java - 从一行中读取特定部分( ""之间)
这个问题已经有答案了: Extract a substring between double quotes with regular expression in Java (2 个回答) how to
php - 在连接表中计算结果并在侧边栏中显示 () 之间
我有一个带有类别的边栏。正如你在这里看到的:http://kees.een-site-bouwen.nl/ url 中类别的 ID。带有 uri 段(3)当您单击其中一个类别时，例如网页设计。显示了一
C++正则表达式搜索多行注释(/* */之间)
这个问题在这里已经有了答案: My regex is matching too much. How do I make it stop? [duplicate] (5 个答案) 关闭 4 年前。我
php - 正则表达式取值在括号 "()"之间？
我很不会写正则表达式。我正在尝试获取括号“()”之间的值。像下面这样的东西...... $a = "POLYGON((1 1,2 2,3 3,1 1))"; preg_match_all("/\((
Android 覆盖在布局边界之外/之间
我必须添加一个叠加层 (ImageView)，以便它稍微移动到包含布局的左边界的左侧。执行此操作的最佳方法是什么？尝试了一些简单的方法，比如将 ImageView 放在布局中并使用负边距 andr
c# - 值与 Rx 之间
Rx 中是否有一些扩展方法来完成下面的场景？我有一个开始泵送的值(绿色圆圈)和其他停止泵送的值(簧片圆圈)，蓝色圆圈应该是预期值，我不希望这个命令被取消并重新创建(即“TakeUntil”和“Ski
r - 检查列值是否在其他两个列值的(范围)之间
我有一个看起来像这样的数据框(Dataframe X): id number found 1 5225 NA 2 2222 NA 3 3121 NA 我有另一个看起来
javascript - 排除 if 之间，但更复杂
所以，我正在尝试制作正则表达式，它将解析存储在对象中的所有全局函数声明，例如，像这样 const a = () => {} 我做了这样的事情: /(?:const|let|var)\s*([A-z0-
javascript - 如何将导弹枪管限制在最小和最大 Angular 之间？
我正在尝试从 Intellivision 重新创建 Astro-Smash，我想让桶保持在两个 Angular 之间。我只是想不出在哪里以及如何让这个东西停留在两者之间。我已经以各种方式交换了函数，
php - 查找选定变量内(之间)的数据总和
到处检查但找不到答案。我有这个页面，我使用 INNER JOIN 将两个表连接在一起，获取它们的值并显示它们。我有这个表格，用来获取变量(例如开始日期、结束日期和卡号)，这些变量将作为从表中调用值的
rust - 夹在一生和 FFI 之间
我陷入了两个不同的问题/错误之间，无法想出一个合适的解决方案。任何帮助将不胜感激上下文、FFI 和调用大量 C 函数，并将 C 类型包装在 rust 结构中。第一个问题是ICE: this pat
MySQL 选择 Current_timestamp 之间
我在 MySQL 中有一个用户列表，在订阅时，时间戳是使用 CURRENT_TIMESTAMP 在数据库中设置的。现在我想从此表中选择订阅日期介于第 X 天和第 Y 天之间的表我尝试了几个查询，但不
java - 如何检查两个日期是否在一个时间段(间隔)之间？
我的输入是开始日期和结束日期。我想检查它是在 12 月 1 日到 3 月 31 日之间。(年份可以更改，并且只有在此期间内或之外的日期)。到目前为止，我还没有找到任何关于 Joda-time 的解决
python - 为什么线程分布在 CPU 之间？
我正在努力了解线程与 CPU 使用率的关系。有很多关于线程与多处理的讨论(一个很好的概述是 this answer )所以我决定通过在运行 Windows 10、Python 3.4 的 8 CPU
PHP do-while 与 HTML 之间
我正在尝试编写 PHP 代码来循环遍历数组以创建 HTML 表格。我一直在尝试做类似的事情: fetchAll(PDO::FETCH_ASSOC); ?>

塔克拉玛干

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

algorithm - 如何计算IP子网之间的差距？