## Thursday, May 17, 2018

### 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:
Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]
Explanation:
The initial ip address, when converted to binary, looks like this (spaces added for clarity):
255.0.0.7 -> 11111111 00000000 00000000 00000111
The address "255.0.0.7/32" specifies all addresses with a common prefix of 32 bits to the given address,

The address "255.0.0.8/29" specifies all addresses with a common prefix of 29 bits to the given address:
255.0.0.8 -> 11111111 00000000 00000000 00001000
Addresses with common prefix of 29 bits are:
11111111 00000000 00000000 00001000
11111111 00000000 00000000 00001001
11111111 00000000 00000000 00001010
11111111 00000000 00000000 00001011
11111111 00000000 00000000 00001100
11111111 00000000 00000000 00001101
11111111 00000000 00000000 00001110
11111111 00000000 00000000 00001111

The address "255.0.0.16/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just 11111111 00000000 00000000 00010000.

In total, the answer specifies the range of 10 ips starting with the address 255.0.0.7 .

There were other representations, such as:
["255.0.0.7/32","255.0.0.8/30", "255.0.0.12/30", "255.0.0.16/32"],
but our answer was the shortest possible.

Also note that a representation beginning with say, "255.0.0.7/30" would be incorrect,
because it includes addresses like 255.0.0.4 = 11111111 00000000 00000000 00000100
that are outside the specified range.

Note:
1. ip will be a valid IPv4 address.
2. Every implied address ip + x (for x < n) will be a valid IPv4 address.
3. n will be an integer in the range [1, 1000].

https://felon03.github.io/2017/12/29/LeetCode-751-IP-to-CIDR/

255.0.0.7/32

8个地址后的IP是255.0.0.16，最后8位是: 00010000，还有4位可以更改

http://www.cnblogs.com/grandyang/p/8440087.html

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
1.     public  List<String> ipToCIDR(java.lang.String ip, int range) {
2.         long x = 0;
3.         //获得一个ip地址每一部分
4.         String[] ips = ip.split("\\.");
5.         //将整ip地址看为一个整体，求出整体的int表示
6.         for (int i = 0; i < ips.length; ++i) {
7.             x = Integer.parseInt(ips[i]) + x * 256;
8.         }
9.         List<String> ans = new ArrayList<>();
10.         while (range > 0) {
11.             //求出二进制表示下的最低有效位的位数能表示的地址的数量
12.             //如果为奇数，则=1，即以原单个起始ip地址为第一块
13.             //如果为偶数，则二进制表示下的最低有效位的位数能表示的地址的数量
14.             long step = x & -x;
15.             //如果大于range，则需要缩小范围
16.             while (step > range) step /= 2;
17.             //不大于需要的range，开始处理
18.             //求出现在能表示的step个地址的地址块
20.             //x加上以求出的地址块
21.             x += step;
22.             //range减去以表示的地址块
23.             range -= step;
24.         }//直到range<0
25.         return ans;
26.     }
27.     static String longToIP(long x, int step) {
28.         int[] ans = new int[4];
29.         //&255操作求出后8位十进制表示
30.         ans[0] = (int) (x & 255);
31.         //右移8位，即求下一个块
32.         x >>= 8;
33.         ans[1] = (int) (x & 255);
34.         x >>= 8;
35.         ans[2] = (int) (x & 255);
36.         x >>= 8;
37.         ans[3] = (int) x;
38.         int len = 33;
39.         //每一位就可以表示2个
40.         while (step > 0) {
41.             len --;
42.             step /= 2;
43.         }
44.         return ans[3] + "." + ans[2] + "." + ans[1] + "." + ans[0] + "/" + len;
45.     }