关于取 ip 补集问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3632 天前的主题，其中的信息可能已经有所发展或是发生改变。

=。=上一贴脑残了。。其实我想问的是取补集问题

上贴联动
http://v2ex.com/t/152080

现在有一部分ip，格式是
1.2.3.4/22
9.10.11.12/23
现在想取他的补集，不知道有什么快捷的方法么 0 0

另外感谢 @orzfly 提供的工具，很有用！

联动

格式

快捷

28 条回复 • 2014-12-08 10:27:16 +08:00

ovear

2014-12-07 03:28:10 +08:00

果然睡得晚会导致智商下降OAQ

ryd994

2014-12-07 09:11:35 +08:00

也是联动上贴，既然交集一定是子集，那补集无非就是往上和往下数而已

LazyZhu

2014-12-07 09:32:27 +08:00

要补集总得有全集吧,请问是哪个:)
0.0.0.0/0
1.0.0.0/7
1.2.0.0/15
1.2.3.0/22

LazyZhu

2014-12-07 09:39:51 +08:00

最小补集的话其实可以从BGP网站查询的,譬如:
http://bgp.he.net/ip/1.2.3.4
http://bgp.he.net/ip/9.10.11.12

Showfom

2014-12-07 10:51:45 +08:00 via iPhone

第一次听到这个词语。。。。。
楼主这叫CIDR 路由器里自己设置的

ovear

2014-12-07 13:23:00 +08:00 via Android

@LazyZhu 全集是0.0.0.0/0也就是所有ip库
算是挖掉一块一块的ip 然后输出新的ip块
oaq
bgphe比较麻烦，因为是通过ip查所属段的问题。。我的是已经知道ip段落
请菊巨指教

@ryd994 交集其实应该是空的说。。

@Showfom 有区别吧，我这个需求比较奇葩

LazyZhu

2014-12-07 13:55:56 +08:00

@ovear
也可以查的
http://bgp.he.net/net/173.194.72.0/24
还有whois也可查bgp

ovear

2014-12-07 14:10:33 +08:00

@LazyZhu =.=貌似这不是补集也。。
其实我就是想要一个算法=。=
怎么在一整段ip里面分割
比如说在所有ip里面
排除 173.194.0.0/16
64.233.165.0/24
这两段
我的想法是首先从开头来找 0.0.0.0 然后找到 173.194.0.0这个首ip，然后想办法用子网掩码近似表示（这个过程不知道是否可行，网基一团糟）

LazyZhu

2014-12-07 14:23:36 +08:00

@ovear 写个perl脚本就可以了
http://search.cpan.org/~andya/Net-CIDR-Set-0.13/lib/Net/CIDR/Set.pm#complement

LazyZhu

2014-12-07 14:36:21 +08:00

@ovear
对了, 你是要单独一个,还是几个的补集?

ryd994

2014-12-07 15:05:53 +08:00

@ovear 交集不一定为空
192.168.0.0/18
192.168.1.0/24
所以我说一定是子集还一定是其中之一

ovear

2014-12-07 15:14:44 +08:00 via Android

@LazyZhu 多个的补集拉

@ryd994 我的ip其实是从bgphe上拉下来的拉所以不会有交集

ryd994

2014-12-07 15:31:16 +08:00

@ovear ipv4 32位，直接一个500M的boolean数组扔过去……
如果知道最大prefix长度还可以减少

ryd994

2014-12-07 15:37:45 +08:00

其实这就是个二分……

Showfom

2014-12-07 15:56:20 +08:00

你自己是找不出来的，因为机房怎么设置的你不知道。。。

LazyZhu

2014-12-07 15:57:19 +08:00

@ovear 还没搞定?
等我烧完菜,帮你写个awk脚本吧
其实用C写性能更好,可惜不会:(

LazyZhu

2014-12-07 16:18:49 +08:00

# cat /tmp/test.list
1.2.3.0/22
9.10.11.0/23
101.120.0.0/14

# cidr_complement.sh
0.0.0.0/8
1.0.0.0/15
1.2.0.0/23
1.2.2.0/24
1.2.7.0/24
1.2.8.0/21
1.2.16.0/20
1.2.32.0/19
1.2.64.0/18
1.2.128.0/17
1.3.0.0/16
1.4.0.0/14
1.8.0.0/13
1.16.0.0/12
1.32.0.0/11
1.64.0.0/10
1.128.0.0/9
2.0.0.0/7
4.0.0.0/6
8.0.0.0/8
9.0.0.0/13
9.8.0.0/15
9.10.0.0/21
9.10.8.0/23
9.10.10.0/24
9.10.13.0/24
9.10.14.0/23
9.10.16.0/20
9.10.32.0/19
9.10.64.0/18
9.10.128.0/17
9.11.0.0/16
9.12.0.0/14
9.16.0.0/12
9.32.0.0/11
9.64.0.0/10
9.128.0.0/9
10.0.0.0/7
12.0.0.0/6
16.0.0.0/4
32.0.0.0/3
64.0.0.0/3
96.0.0.0/6
100.0.0.0/8
101.0.0.0/10
101.64.0.0/11
101.96.0.0/12
101.112.0.0/13
101.124.0.0/14
101.128.0.0/9
102.0.0.0/7
104.0.0.0/5
112.0.0.0/4
128.0.0.0/0

需要其他编程语言的话,参照这个改一下就ok了

代码:
https://gist.github.com/LazyZhu/3f15cf7ab3777b54d21c

ovear

2014-12-07 18:54:23 +08:00

@LazyZhu 感谢OAQ，简直男神。。

ericFork

2014-12-07 19:24:27 +08:00

难道需求是取逆·chnroutes?

ovear

2014-12-07 19:30:00 +08:00

@ericFork 类似吧。。跟我一个小项目有关-0-

ericFork

2014-12-07 19:31:06 +08:00

@ovear 目前我有逆 chnroutes 的需求……

ovear

2014-12-07 19:46:49 +08:00

@ericFork 0 0逆那个干嘛。。有现成的项目
https://github.com/ovear/bestroutetb

ovear

2014-12-07 20:00:28 +08:00

@LazyZhu 大神。。报错了肿么办

awk: -:2: for (ret=0,n=split(ip,a,"\."),x=1;x<=n;x++) ret=or(lshift(ret,8),a[x])
awk: -:2: ^ syntax error
awk: -:2: warning: escape sequence `\.' treated as plain `.'
awk: -:2: for (ret=0,n=split(ip,a,"\."),x=1;x<=n;x++) ret=or(lshift(ret,8),a[x])
awk: -:2: ^ syntax error
awk: -:2: for (ret=0,n=split(ip,a,"\."),x=1;x<=n;x++) ret=or(lshift(ret,8),a[x])
awk: -:2: ^ syntax error
awk: -:9: for(;x<3;ret=and(ip,255)"."ret,ip=rshift(ip,8),x++);
awk: -:9: ^ syntax error
awk: -:9: for(;x<3;ret=and(ip,255)"."ret,ip=rshift(ip,8),x++);
awk: -:9: ^ syntax error

ericFork

2014-12-08 01:46:31 +08:00

@ovear 我的需求是让中国 IP 段走 VPN，翻回国内……

ericFork

2014-12-08 02:03:56 +08:00

@ovear 原来这个项目进化了，看起来可以直接用了！

LazyZhu

2014-12-08 09:47:39 +08:00

@ovear 只是awk语法格式的兼容问题,会的话自己改一下吧;不会的话我中午抽空改一下.

Showfom

2014-12-08 10:25:09 +08:00 via iPhone

@ericFork 弄好给我用用

ovear

2014-12-08 10:27:16 +08:00 via Android

@LazyZhu 改好啦我晚点方gist上
不过貌似有不可见的bug
我晚上回去研究下