请教airbnb IP CIDR这道题

快要onsite了 IP CIDR这道题在好几个面经都有看到 但是都没有讲具体思路是什么 网上搜了搜只有一个很tricky的解法感觉根本不明白 求哪位大神能指点一二 拜谢

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
style="color:rgb(255, 255, 255)">
然后给你一个起始ip，和数量。用最少的cidr表示这个区间

我来做个搬运工。。。

1. import java.util.ArrayList;
   
2. import java.util.List;
   
3. 
   
4. public class RangeToCidr {
   
5.     public static List<String> range2cidrlist( String startIp, String endIp ) {
   
6.         // check parameters
   
7.         if (startIp == null || startIp.length() < 8 ||
   
8.             endIp == null || endIp.length() < 8) return null;
   
9.         long start = ipToLong(startIp);
   
10.         long end = ipToLong(endIp);
    
11.         // check parameters
    
12.         if (start > end) return null;
    
13. 
    
14.         List<String> result = new ArrayList<String>();
    
15.         while (start <= end) {
    
16.             // identify the location of first 1's from lower bit to higher bit of start IP
    
17.             // e.g. 00000001.00000001.00000001.01101100, return 4 (100)
    
18.             long locOfFirstOne = start & (-start);
    
19.             int maxMask = 32 - (int) (Math.log(locOfFirstOne) / Math.log(2));
    
20. 
    
21.             // calculate how many IP addresses between the start and end
    
22.             // e.g. between 1.1.1.111 and 1.1.1.120, there are 10 IP address
    
23.             // 3 bits to represent 8 IPs, from 1.1.1.112 to 1.1.1.119 (119 - 112 + 1 = 8)
    
24.             double curRange = Math.log(end - start + 1) / Math.log(2);
    
25.             int maxDiff = 32 - (int) Math.floor(curRange);
    
26. 
    
27.             // why max?
    
28.             // if the maxDiff is larger than maxMask
    
29.             // which means the numbers of IPs from start to end is smaller than mask range
    
30.             // so we can't use as many as bits we want to mask the start IP to avoid exceed the end IP
    
31.             // Otherwise, if maxDiff is smaller than maxMask, which means number of IPs is larger than mask range
    
32.             // in this case we can use maxMask to mask as many as IPs from start we want.
    
33.             maxMask = Math.max(maxDiff, maxMask);
    
34. 
    
35.             // Add to results
    
36.             String ip = longToIP(start);
    
37.             result.add(ip + "/" + maxMask);
    
38.             // We have already included 2^(32 - maxMask) numbers of IP into result
    
39.             // So the next round start must add that number
    
40.             start += Math.pow(2, (32 - maxMask));
    
41.         }
    
42.         return result;
    
43.     }
    
44. 
    
45.     private static long ipToLong(String strIP) {
    
46.         String[] ipSegs = strIP.split("\\.");
    
47.         long res = 0;
    
48.         for (int i = 0; i < 4; i++) {
    
49.             res += Long.valueOf(ipSegs[i]) << (8 * (3 - i));
    
50.         }
    
51.         return res;
    
52.     }
    
53. 
    
54.     private static String longToIP(long longIP) {
    
55.         StringBuffer sb = new StringBuffer();
    
56.         sb.append(longIP >>> 24).append(".")
    
57.           .append((longIP & 0x00FFFFFF) >>> 16).append(".")
    
58.           .append(String.valueOf((longIP & 0x0000FFFF) >>> 8)).append(".")
    
59.           .append(String.valueOf(longIP & 0x000000FF));
    
60. 
    
61.         return sb.toString();
    
62.     }
    
63. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lz求电面和skype的题目

goodluck888 发表于 2016-12-8 06:32
lz求电面和skype的题目

我不是new grad 店面就是2D数组那道

http://stackoverflow.com/questions/5020317/in-java-given-an-ip-address-range-return-the-minimum-list-of-cidr-blocks-that

我看的这个解法，然后自己研究了一下改了改～

http://stackoverflow.com/questions/33443914/how-to-convert-ip-address-range-to-cidr-in-java

gy21 发表于 2016-12-9 03:20
http://stackoverflow.com/questions/33443914/how-to-convert-ip-address-range-to-cidr-in-java

谢谢 这个好理解多了！

XCQ 发表于 2016-12-8 11:53
谢谢 这个好理解多了！

那个first1的location是100（4）你怎么理解的呢？

gy21 发表于 2016-12-8 12:05
那个first1的location是100（4）你怎么理解的呢？

取反+1再ANd就会得到4.。自问自答下。