Given a range of consecutive IP, return the least amount of CIDR IPs needed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package airbnb;

import java.util.LinkedList;
import java.util.List;


/**
* 输入一个ip,和一个count来表示一组ip, e.g.   7.7.7.7和3表示 7.7.7.7, 7.7.7.8, 7.7.7.9,
* 输出这组ip的CIDR形式.CIDR表达是: ip地址/掩码位数 表示一个区间
* 比如 0.0.0.8 / 30 就是以0.0.0.8为准,前30位不能变--》0.0.0.(0000 10 00)--0.0.0.(0000 10 11)
* 然后给你一个起始ip,和数量。用最少的cidr表示这个区间
* @author yihuifu
*
*/

public class CIDR {

public static void main(String[] args) {
String ip = "7.7.7.7";
int count = 3;
CIDR cidr = new CIDR();
String binaryIP = cidr.decimalToBinary(ip);
List<String> cidrs = new LinkedList<>();
cidr.getCIDRS(binaryIP, count, cidrs);
for (String cidrIP : cidrs) {
System.out.println(cidrIP);
}
}

public void getCIDRS(String binaryIP, int count, List<String> res) {
while (count > 0) {
int zero = 0, last = binaryIP.length() - 1;
while (last >= 0 && binaryIP.charAt(last) == '0') {
if (count - (int) Math.pow(2, zero + 1) >= 0) {
zero++;
last--;
} else {
break;
}
}
String cidrIP = binaryToDecimal(binaryIP) + "/" + (32 - zero);
System.out.println("Found one CIDR " + cidrIP);
res.add(cidrIP);
count -= (int) Math.pow(2, zero);
binaryIP = getNextBinaryIP(binaryIP, zero);
}

}

public String getNextBinaryIP(String prevIp, int lastZero) {
System.out.println("prevIP " + prevIp);
int one = 32 - 1 - lastZero;
while (one >= 0 && prevIp.charAt(one) == '1') {
one--;
}
StringBuilder res = new StringBuilder(prevIp.substring(0, one));
res.append("1");
while (res.length() < 32) {
res.append("0");
}
return res.toString();
}

public String binaryToDecimal(String binaryIP) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < binaryIP.length(); i += 8) {
String subBinary;
if (i < 24) {
subBinary = binaryIP.substring(i, i + 8);
} else {
subBinary = binaryIP.substring(i);
}

Integer sub = Integer.parseInt(subBinary, 2);
sb.append(sub);
if (i < 24) {
sb.append(".");
}
}
System.out.println("convert " + binaryIP + " to " + sb.toString());
return sb.toString();
}

public String decimalToBinary(String decimalIP) {
StringBuilder sb = new StringBuilder();
String[] ips = decimalIP.split("\\.");
for (int i = 0; i < ips.length; i++) {
Integer sub = Integer.parseInt(ips[i]);
String binarySub = Integer.toBinaryString(sub);
int missingDigit = 8 - binarySub.length();
String zeros = "";
while (missingDigit > 0) {
zeros += "0";
missingDigit--;
}
sb.append(zeros + binarySub);
}
System.out.println("convert " + decimalIP + " to " + sb.toString());
return sb.toString();
}

}