http://bookshadow.com/weblog/2017/12/24/leetcode-ip-to-cidr/
https://blog.csdn.net/qq_32832023/article/details/78891298
https://freedomly.tk/2017/12/29/LeetCode-751-IP-to-CIDR/
Given a start IP address
ip
and a number of ips we need to cover n
, return a representation of the range as a list (of smallest possible length) of CIDR blocks.
A CIDR block is a string consisting of an IP, followed by a slash, and then the prefix length. For example: "123.45.67.89/20". That prefix length "20" represents the number of common prefix bits in the specified range.
Example 1:
Note:
ip
will be a valid IPv4 address.- Every implied address
ip + x
(forx < n
) will be a valid IPv4 address. n
will be an integer in the range[1, 1000]
.
将起始ip转为int,遍历[ipInt, ipInt + range)
假设当前遍历到了第x个ip地址,记cIpInt = ipInt + x
计算cIpInt末尾0的个数,记为zeros,重复将zeros-1,直到x + 1<<zeros不大于range为止
将ipInt复原为IP地址 / 32 - zeros加入结果列表
https://felon03.github.io/2017/12/29/LeetCode-751-IP-to-CIDR/
这个问题是在给定的起始IP地址,求最少的CIDR正好覆盖n个IP地址。所求的地址要求是连续的,并且要在起始IP的后面。
先说明一下
一个IPv4的地址总共有32位,可以表示29表示的是IP的前29为是固定的,后三位可以改变,因此可以覆盖(8)个IP。那么要使CIDR尽量的少,就让固定的IP的位数尽量少,同时要保证IP是连续的。
255.255.0.8/29
中29的含义:一个IPv4的地址总共有32位,可以表示29表示的是IP的前29为是固定的,后三位可以改变,因此可以覆盖(8)个IP。那么要使CIDR尽量的少,就让固定的IP的位数尽量少,同时要保证IP是连续的。
比如我们以
255.0.0.7
开始,覆盖30个地址,那么就有:http://www.cnblogs.com/grandyang/p/8440087.html255.0.0.7/32
只有一个IP地址 剩余30 - 1 = 29接下来的IP地址是 255.0.0.8,最后8位是: 00001000,还有3位可以更改
则有255.0.0.8/29 可以覆盖8个IP,剩余29 - 8 = 218个地址后的IP是255.0.0.16,最后8位是: 00010000,还有4位可以更改
则有255.0.0.16/28 可以覆盖16个IP,剩余21 - 16 = 5接下来的IP地址是255.0.0.32,最后8位是: 00100000,还有5位可以更改,而剩余的要覆盖的IP只有5个,因此要小于5,否则覆盖的IP范围就会超过给定的个数,因此是4个,即对最后两位进行更改
则有255.0.0.32/30 可以覆盖4个IP,剩余5 - 4 = 1那么最后一个要覆盖的就是255.0.0.36/32,剩余0个要覆盖
至此可以得到最少的CIDR。
此题给了我们一个用字符串表示的ip地址,还有一个整数n,让我们以给定的ip地址为起点,需要覆盖n个ip地址。而这n个ip地址的写法使用无类别域间路由CIDR块来写,所谓的CIDR块,是由一个正常的ip地址,加上斜杠数字,斜杠后面的数字表示这些ip地址具有相同的前缀的个数,比如"255.0.0.7/32",如果有32个相同的前缀,说明只有唯一的一个ip地址,因为IPv4总共就只有32位。再比如"255.0.0.8/29",表示有29个相同的前缀,那么最后3位可以自由发挥,2的3次方为8,所以就共有8个ip地址。同理,"255.0.0.16/32"只表示一个地址,那么这三个CIDR块总共覆盖了10个地址,就是我们要求的结果。
由于题目中要求尽可能少的使用CIDR块,那么在n确定的情况下,CIDR块能覆盖的越多越好。根据我们前面的分析,当CIDR块斜杠后面的数字越小,该块覆盖的ip地址越多。那么就是说相同前缀的个数越少越好,但是我们的ip地址又不能小于给定的ip地址,所以我们只能将0变为1,而不能将1变为0。所以我们的选择就是有将最低位1后面的0进行变换,比如"255.0.0.8"末尾有3个0,可以变换出8个不同的地址。那么我们只要找出末尾1的位置,就知道能覆盖多少个地址了。找末尾1有个trick,就是利用 x & -x 来快速找到,这个trick在之前做的题中也有应用。知道了最多能覆盖地址的数量,还要考虑到n的大小,不能超过n,因为题目只要求覆盖n个。确定了覆盖的个数,我们就可以进行生成CIDR块的操作了,之前我们为了求 x & -x,将ip地址转为了一个十进制的数,现在我们要把每一块拆分出来,直接按对应位数量进行右移并与上255即可,斜杠后的数字计算通过覆盖的个数进行log2运算,再被32减去即可
vector<string> ipToCIDR(string ip, int n) { vector<string> res; long x = 0; istringstream is(ip); string t; while (getline(is, t, '.')) { x = x * 256 + stoi(t); } while (n > 0) { long step = x & -x; while (step > n) step /= 2; res.push_back(convert(x, step)); x += step; n -= step; } return res; } string convert(long x, int step) { return to_string((x >> 24) & 255) + "." + to_string((x >> 16) & 255) + "." + to_string((x >> 8) & 255) + "." + to_string(x & 255) + "/" + to_string(32 - (int)log2(step)); }https://zhuanlan.zhihu.com/p/35541808
public static void main(String[] args) {
IP2CIDR i2 = new IP2CIDR();
System.out.println(i2.IC("255.0.0.7", 10));
}
public String IC(String ip,int n){
//思路,找到这些IPs中从右往左第一位相同的二进制位
// x & -x ;-x是x的补码,返回x与2^64的最大公约数,
//即x最多能被n个2整除就返回2^n,如果x是奇数返回1;返回值为0 ,说明x=0;为其他数,表示x为x与2^64的最大公约数
//一言以蔽之就是获取32位二进制表示中从右往左首次出现1的位置
long x = 0;
//以"."划分每个IP
String[] ipsegment = ip.split("\\.");
for(int i=0;i<ipsegment .length;i++){
x = Integer.parseInt(ipsegment [i])+x*256;
}
String res = "";
while(n>0){
long temp = x & -x;//求得该IP用32位二进制表示中从右往左首次出现1的位置
//-x才是x的补码,~x为反码
//temp如果为奇数,则该IP为第一个CIDR块
//如果偶数,则该IP用二进制表示下的最低有效位的位数能表示的地址的数量
while(temp>n) {
temp = temp/2;
}
//到这里temp肯定是小于n的,这告诉我们包括此IP在内的temp个IPs可以用一个ICDR来表示
//接下来求出这些IPs所处的CIDR
res+=longToIP(x, (int)temp)+" ";
//x加上temp;
x+=temp;//temp个ips考虑好了,接下来考虑从x+temp考虑
n-=temp;//还有几个IPs要求ICDR的
}
return res;
}
public String longToIP(long x,int temp){
int netID = 32;
while(temp>0){
temp/=2;
netID--;
}
int[] ans = new int[4];
for(int i=0;i<ans.length-1;i++){
ans[i] = (int)(x & 255);
x>>=8;
}
ans[ans.length-1] = (int)x;
netID++; //加1:比如说某些IPs有m位相同,是指0-m-1位相同
return ans[3]+"."+ans[2]+"."+ans[1]+"."+ans[0]+"/"+netID;
}
https://blog.csdn.net/qq_32832023/article/details/78891298- public List<String> ipToCIDR(java.lang.String ip, int range) {
- long x = 0;
- //获得一个ip地址每一部分
- String[] ips = ip.split("\\.");
- //将整ip地址看为一个整体,求出整体的int表示
- for (int i = 0; i < ips.length; ++i) {
- x = Integer.parseInt(ips[i]) + x * 256;
- }
- List<String> ans = new ArrayList<>();
- while (range > 0) {
- //求出二进制表示下的最低有效位的位数能表示的地址的数量
- //如果为奇数,则=1,即以原单个起始ip地址为第一块
- //如果为偶数,则二进制表示下的最低有效位的位数能表示的地址的数量
- long step = x & -x;
- //如果大于range,则需要缩小范围
- while (step > range) step /= 2;
- //不大于需要的range,开始处理
- //求出现在能表示的step个地址的地址块
- ans.add(longToIP(x, (int)step));
- //x加上以求出的地址块
- x += step;
- //range减去以表示的地址块
- range -= step;
- }//直到range<0
- return ans;
- }
- static String longToIP(long x, int step) {
- int[] ans = new int[4];
- //&255操作求出后8位十进制表示
- ans[0] = (int) (x & 255);
- //右移8位,即求下一个块
- x >>= 8;
- ans[1] = (int) (x & 255);
- x >>= 8;
- ans[2] = (int) (x & 255);
- x >>= 8;
- ans[3] = (int) x;
- int len = 33;
- //每一位就可以表示2个
- while (step > 0) {
- len --;
- step /= 2;
- }
- return ans[3] + "." + ans[2] + "." + ans[1] + "." + ans[0] + "/" + len;
- }
private long ipToLong(String strIP) {
long[] ip = new long[4];
String[] ipSec = strIP.split("\\.");
for (int k = 0; k < 4; k++) {
ip[k] = Long.valueOf(ipSec[k]);
}
return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];
}
private String longToIP(long longIP) {
StringBuffer sb = new StringBuffer("");
sb.append(String.valueOf(longIP >>> 24));
sb.append(".");
sb.append(String.valueOf((longIP & 0x00FFFFFF) >>> 16));
sb.append(".");
sb.append(String.valueOf((longIP & 0x0000FFFF) >>> 8));
sb.append(".");
sb.append(String.valueOf(longIP & 0x000000FF));
return sb.toString();
}
public List<String> ipRange2Cidr(String startIp, int range) {
// check parameters
String a = "";
long start = ipToLong(startIp);
long end = start + range - 1;
List<String> res = new ArrayList<>();
while (start <= end) {
// identify the location of first 1's from lower bit to higher bit of start IP
// e.g. 00000001.00000001.00000001.01101100, return 4 (100)
long locOfFirstOne = start & (-start);
int curMask = 32 - (int) (Math.log(locOfFirstOne) / Math.log(2));
// calculate how many IP addresses between the start and end
// e.g. between 1.1.1.111 and 1.1.1.120, there are 10 IP address
// 3 bits to represent 8 IPs, from 1.1.1.112 to 1.1.1.119 (119 - 112 + 1 = 8)
double currRange = Math.log(end - start + 1) / Math.log(2);
int currRangeMask = 32 - (int) Math.floor(currRange);
// why max?
// if the currRangeMask is larger than curMask
// which means the numbers of IPs from start to end is smaller than mask range
// so we can't use as many as bits we want to mask the start IP to avoid exceed the end IP
// Otherwise, if currRangeMask is smaller than curMask, which means number of IPs is larger than mask range
// in this case we can use curMask to mask as many as IPs from start we want.
curMask = Math.max(currRangeMask, curMask);
// Add to results
String ip = longToIP(start);
res.add(ip + "/" + curMask);
// We have already included 2^(32 - curMask) numbers of IP into result
// So the next roundUp start must insert that number
start += Math.pow(2, (32 - curMask));
}
return res;
}
做本题需要一些IP地址的知识,还要理解 16 行的x&-x 操作的含义。
!最好自己先思考一下,对基本的可能出现的情况有一个了解。
比如IP地址的最后一块是奇数/偶数的情况;IP地址块扩大时能容纳的数量和n的关系等。
比如IP地址的最后一块是奇数/偶数的情况;IP地址块扩大时能容纳的数量和n的关系等。
public List<String> ipToCIDR(java.lang.String ip, int range) {
long x = 0;
// 获得一个ip地址每一部分
String[] ips = ip.split("\\.");
// 将整ip地址看为一个整体,求出整体的int表示
for (int i = 0; i < ips.length; ++i) {
x = Integer.parseInt(ips[i]) + x * 256;
}
List<String> ans = new ArrayList<>();
while (range > 0) {
// 求出二进制表示下的最低有效位的位数能表示的地址的数量
// 如果为奇数,则=1,即以原单个起始ip地址为第一块
// 如果为偶数,则二进制表示下的最低有效位的位数能表示的地址的数量
long step = x & -x;
// 如果大于range,则需要缩小范围
while (step > range)
step /= 2;
// 不大于需要的range,开始处理
// 求出现在能表示的step个地址的地址块
ans.add(longToIP(x, (int) step));
// x加上以求出的地址块
x += step;
// range减去以表示的地址块
range -= step;
} // 直到range<0
return ans;
}
static String longToIP(long x, int step) {
int[] ans = new int[4];
// &255操作求出后8位十进制表示
ans[0] = (int) (x & 255);
// 右移8位,即求下一个块
x >>= 8;
ans[1] = (int) (x & 255);
x >>= 8;
ans[2] = (int) (x & 255);
x >>= 8;
ans[3] = (int) x;
int len = 33;
// 每一位就可以表示2个
while (step > 0) {
len--;
step /= 2;
}
return ans[3] + "." + ans[2] + "." + ans[1] + "." + ans[0] + "/" + len;
}
https://uule.iteye.com/blog/2102484https://freedomly.tk/2017/12/29/LeetCode-751-IP-to-CIDR/
|