昨天面试的时候,面试官出了一道算法题,当时头脑有点乱,没有想出来,现在把它写出来
题目:给定几个白名单网段,例如 "172.16.0.0/17", "192.168.0.0/24", "10.10.10.10/9",现在有个请求过来,怎么快速确认请求IP是否在白名单中?
package common; import org.junit.Test; public class WhiteListTest { private String[] whiteList = { "172.16.0.0/17", "192.168.0.0/24", "10.10.10.10/9" }; @Test public void test() { String testIp = "192.168.0.1"; for (String net : whiteList) { NetworkOffset offset = new NetworkOffset(net); System.out.println(offset); if (offset.matches(testIp)) { System.out.println("found"); } } } private static class NetworkOffset { private int mask; private int baseIp; NetworkOffset(String net) { init(net); } private void init(String net) { mask = Integer.valueOf(net.split("/")[1]); mask = 0xFFFFFFFF << (32-mask); String address = net.split("/")[0]; baseIp = parseAddr(address); } boolean matches(int ip) { return (baseIp & mask) == (ip & mask); } boolean matches(String ip) { return matches(parseAddr(ip)); } private int parseAddr(String addr) { String[] array = addr.split("\\."); int ip = 0; for (int i = 0; i < array.length; i++) { int part = (Integer.parseInt(array[i]) & 0xFF) << (24 - 8 * i); ip = ip | part; } return ip; } String first() { int firstIp = baseIp & mask | 0x01; return toIpString(firstIp); } String last() { int lastIp = baseIp & mask | (~mask & 0xFFFFFFFE); return toIpString(lastIp); } private String toIpString(int ip) { String part1 = String.valueOf(ip >> 24 & 0xFF); String part2 = String.valueOf(ip >> 16 & 0xFF); String part3 = String.valueOf(ip >> 8 & 0xFF); String part4 = String.valueOf(ip & 0xFF); return part1 + "." + part2 + "." + part3 + "." + part4; } String broadcast() { int broadcastIp = baseIp & mask | (~mask); return toIpString(broadcastIp); } @Override public String toString() { return "NetworkOffset [mask=" + Integer.toBinaryString(mask) + ", baseIp=" + Integer.toBinaryString(baseIp) + ", firstIp=" + first() + ", lastIp=" + last() + ", broadcastIp=" + broadcast() + "]"; } } }