题解 | #识别有效的IP地址和掩码并进行分类统计#
识别有效的IP地址和掩码并进行分类统计
https://www.nowcoder.com/practice/de538edd6f7e4bc3a5689723a7435682
此题目有坑QAQ！
每一行分割出ip和mask，进行判断。
下面是解题思路，顺序不能乱：
- 输入空行要忽略
- ip以0.*或者127.*开头则忽略，无论其格式、长度是否正确，无论子网掩码是否正确，都跳过
- 判断分割后的ip或子网掩码是否合法，任意其中一个不合法（不能重复记录），则记录一条错误ip
- 进行ip归类：A、B、C、D、E、私有IP
坑在哪里呢？
1️⃣ 只要是0.*、127.*开头，都得忽略，无论它是否合法
2️⃣ 按"."分割后的段，不能为空串或空白，如果是空白的话不合法，段数不为4不合法，少了多了都不行
归类技巧：我在这里用了ip转int，类似于c++中的aton函数，将合法ip地址转换为int，判断其大小是否在对应的归类区间内即可！
对于子网掩码的判断，需要将其转换成bit字符串或者bit数组，然后判断是否全0、全1，以及第一个0之后是否还有1。
找到第一个0，然后判断后面是否还有1即可。
一开始我想着用BitSet，把ip切分：
public static boolean isValidMask(String ip){
String[] ipSplits = ip.split("\\.");
byte[] bytes = new byte[4];
for(int i=0; i<4; i++){
bytes[i] = (byte)Short.parseShort(ipSplits[i]);
}
BitSet bits = BitSet.valueOf(bytes);
// 全1或者全0的子网掩码非法
if (bitSet.cardinality() == 32 || bitSet.cardinality() == 0) {
return false;
}
// 本以为这样没有任何问题
int firstClearIndex = bitSet.nextClearBit(0);
int lastSetIndex = bitSet.nextSetBit(firstClearIndex);
if (lastSetIndex != -1) {
return false;
}
return true;
}
本来上述代码个人认为没问题的，结果提交后运行到6/10组测试用例时出错了，多统计了一个错误ip地址！
找了别人的代码，输出了相关的wrongIP列表，发现是
6.72.161.12~255.252.0.0
这条输入的子网掩码255.252.0.0，通过上述代码转换后的bitSet值为：{0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15}
然后才发现了问题，252被转换成了00111111，也就是十进制63，然而我的bytes数组值是：[-1, -4, 0, 0]
这里就很奇怪！！！！！！
debug找到BitSet.valueOf看源码：
发现这里用了一个long[] words来记录所有的bit位，bb = [-1, -4, 0, 0]，传过来后计算出来n=2，也就是非0 byte的个数。
bb做了切片排序，排序规则是字节的小端存储格式，也就是说低位在前，高位在后。
循环中依次取值-1、-4，做运算：(-1 & 0xffL) << 0 和 (-4 & 0xffL) << 8 并分别将结果通过或运算放到words[i]中（一个long 64位）；计算出来的words值是64767，也就是二进制11111100 11111111。好了，找到了问题所在！就是这里运算出了问题。
由于采用的是小端存储模式，计算出来的结果是64767，即二进制11111100 11111111。
但是实际上我们要的二进制是11111111 11111100，也就是255 << 8 | 252。
真是坑爹的玩意儿！好吧，是我对BitSet不够熟悉了，导致用起来折磨了我几个小时。后续再好好研究下怎么使用BitSet吧。
最后使用Integer.toBinaryString(ip)转换成二进制字符串解决了问题。
贴代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
long[][] ipClasses = new long[5][2];
//A类地址从1.0.0.0到126.255.255.255;
ipClasses[0] = new long[]{
parseIPToLong("1.0.0.0"),
parseIPToLong("126.255.255.255")
};
//B类地址从128.0.0.0到191.255.255.255;
ipClasses[1] = new long[]{
parseIPToLong("128.0.0.0"),
parseIPToLong("191.255.255.255")
};
//C类地址从192.0.0.0到223.255.255.255;
ipClasses[2] = new long[]{
parseIPToLong("192.0.0.0"),
parseIPToLong("223.255.255.255")
};
//D类地址从224.0.0.0到239.255.255.255；
ipClasses[3] = new long[]{
parseIPToLong("224.0.0.0"),
parseIPToLong("239.255.255.255")
};
//E类地址从240.0.0.0到255.255.255.255
ipClasses[4] = new long[]{
parseIPToLong("240.0.0.0"),
parseIPToLong("255.255.255.255")
};
long[][] privateIp = new long[3][2];
//私网IP范围是：
//从10.0.0.0到10.255.255.255
//从172.16.0.0到172.31.255.255
//从192.168.0.0到192.168.255.255
privateIp[0] = new long[]{
parseIPToLong("10.0.0.0"),
parseIPToLong("10.255.255.255")
};
privateIp[1] = new long[]{
parseIPToLong("172.16.0.0"),
parseIPToLong("172.31.255.255")
};
privateIp[2] = new long[]{
parseIPToLong("192.168.0.0"),
parseIPToLong("192.168.255.255")
};
Scanner in = new Scanner(System.in);
//ArrayList<String> wrongList = new ArrayList<>();
int[] classesCount = new int[5];
int wrongIp = 0;
int privateCount = 0;
while (in.hasNextLine()) {
String line = in.nextLine();
if (line.trim().isEmpty()) {
continue;
}
String[] ips = line.split("\\~");
// ip以0.*或者127.*开头则忽略，无论其格式、长度是否正确，无论子网掩码是否正确
if (ips[0].startsWith("0.") || ips[0].startsWith("127.")) {
continue;
}
boolean validIP = isValidIP(ips[0]);
boolean validMask = isValidMask(ips[1]);
if (!validIP || !validMask) { // ip或子网掩码不正确，记录一条错误ip
//wrongList.add(line);
wrongIp++;
continue;
}
long ip = parseIPToLong(ips[0]);
// 进行归类
for (int i = 0; i < 5; i++) {
if (ipClasses[i][0] <= ip && ip <= ipClasses[i][1]) {
classesCount[i] += 1;
break;
}
}
for (int i = 0; i < 3; i++) {
if (privateIp[i][0] <= ip && ip <= privateIp[i][1]) {
privateCount++;
break;
}
}
}
for (int i = 0; i < 5; i++) {
System.out.printf("%d ", classesCount[i]);
}
System.out.printf("%d %d\n", wrongIp, privateCount);
//wrongList.forEach(System.out::println);
}
public static boolean isValidIP(String ipStr) {
String[] ipSplits = ipStr.split("\\.");
if (ipSplits.length != 4) {
return false;
}
for (int i = 0; i < ipSplits.length; i++) {
if (ipSplits[i].trim().isEmpty()) { // 不合法的ip地址
return false;
}
short num = Short.parseShort(ipSplits[i]);
if (num > 255 || num < 0) {
return false;
}
}
return true;
}
public static boolean isValidMask(String ipStr) {
if (!isValidIP(ipStr)) {
return false;
}
int ip = (int) parseIPToLong(ipStr);
int bitCount = Integer.bitCount(ip);
if (bitCount == 32 || bitCount == 0) {
return false;
}
String bits = Integer.toBinaryString(ip);
int firstClearIndex = bits.indexOf('0');
int lastSetIndex = bits.indexOf('1', firstClearIndex);
if (lastSetIndex != -1) {
return false;
}
return true;
}
public static long parseIPToLong(String ipStr) {
String[] ipSplits = ipStr.split("\\.");
int[] ip = Arrays.stream(ipSplits).mapToInt(Integer::valueOf).toArray();
return ((long) ip[0] << 24L) + ((long) ip[1] << 16) + ((long) ip[2] << 8) + ip[3];
}
}
后续：
==========贴一下bitset排查问题记============
我模拟了一下bitset内部使用ByteBuffer构造的逻辑，
然后得到的输出是：
然后我把运算逻辑的左移换了一下，将 << 8 * i 改成 << 8 * ( 3 - i )，测试结果如下：
输出结果：
我直呼好家伙！！！！原来如此！！！这不才是我想要的吗？
从高位31位到低位18为全1，低17位至低1位为0。
不过BitSet输出的位置和我理解的不一样，我本理解是大端模式的存储，结果它依然底层是小端模式的存储，高位在后，低位在前！
我们通常是以大端存储的视角看整个ip的bit位情况，因此需要转换一下思路：
int firstZeroIndex = bits.previousClearBit(31);
System.out.println("第一个0位置：" + firstZeroIndex);
int lastOneIndex = bits.previousSetBit(firstZeroIndex);
System.out.println("最后一个1位置：" + lastOneIndex);
首先使用bits.previousClearBit(31);来获取高位31往低位方向的第一个0位置，然后使用bits.previousSetBit(firstZeroIndex)来获取0位置之后低位的1位置有没有。
输出结果：
可以看到没有找到，返回的是-1，符合我们的预期。
接下来换成"255.252.0.1"这个非法的子网掩码看下结果：
第一个0位置是第17bit位，而在17bit位之后的第一个1位置是第0bit位。这样就符合预期了！
既然已经知道了BitSet是采用小端地址格式来存储的，那么最后再来对byte数组做一下验证（把bytes数组倒序存放ip段）：
输出结果如下：
这样才能完美实现利用BitSet来判断高位0和低位1的位置情况了。
所以就是谨记一点：如果使用BitSet，那么一定要记住，它是小端地址存储格式的！！！！
总结来说，是自己太菜了，不熟悉bitset导致多花了很多时间，不过确实也学到了bitset的用法，以后不会再踩坑了。
查看3道真题和解析