欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

过滤白名单算法

程序员文章站 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() + "]";
		}

	}
}


相关标签: 算法 白名单