过滤白名单算法
程序员文章站
2022-05-19 10:11:13
...
昨天面试的时候,面试官出了一道算法题,当时头脑有点乱,没有想出来,现在把它写出来
题目:给定几个白名单网段,例如 "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() + "]";
}
}
}
上一篇: Shiro授权