关于取 ip 补集问题

[ovear]

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

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

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

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

[ovear]

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

[ryd994]

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

[LazyZhu]

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

[LazyZhu]

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

[Showfom]

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

[ovear]

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

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

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

[LazyZhu]

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

[ovear]

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

[LazyZhu]

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

[LazyZhu]

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

[ryd994]

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

[ovear]

@LazyZhu 多个的补集拉

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

[ryd994]

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

[ryd994]

其实这就是个二分……

[Showfom]

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

[LazyZhu]

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

[LazyZhu]

# 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]

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

[ericFork]

难道需求是取 逆·chnroutes?

[ovear]

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

[ericFork]

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

[ovear]

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

[ovear]

@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]

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

[ericFork]

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

[LazyZhu]

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

[Showfom]

@ericFork 弄好给我用用

[ovear]

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