过滤白名单算法

时间:2022-09-11 13:17:51

昨天面试的时候,面试官出了一道算法题,当时头脑有点乱,没有想出来,现在把它写出来

题目:给定几个白名单网段,例如 "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() + "]";
		}

	}
}