Given a start IP addressipand a number of ips we need to covern, return a representation of the range as a list (of smallest possible length) of CIDR blocks.

A CIDR block is a string consisting of an IP, followed by a slash, and then the prefix length. For example: "123.45.67.89/20". That prefix length "20" represents the number of common prefix bits in the specified range.

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]
Explanation:
The initial ip address, when converted to binary, looks like this (spaces added for clarity):
255.0.0.7 -> 11111111 00000000 00000000 00000111
The address "255.0.0.7/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just this one address.

The address "255.0.0.8/29" specifies all addresses with a common prefix of 29 bits to the given address:
255.0.0.8 -> 11111111 00000000 00000000 00001000
Addresses with common prefix of 29 bits are:
11111111 00000000 00000000 00001000
11111111 00000000 00000000 00001001
11111111 00000000 00000000 00001010
11111111 00000000 00000000 00001011
11111111 00000000 00000000 00001100
11111111 00000000 00000000 00001101
11111111 00000000 00000000 00001110
11111111 00000000 00000000 00001111

The address "255.0.0.16/32" specifies all addresses with a common prefix of 32 bits to the given address,
ie. just 11111111 00000000 00000000 00010000.

In total, the answer specifies the range of 10 ips starting with the address 255.0.0.7 .

There were other representations, such as:
["255.0.0.7/32","255.0.0.8/30", "255.0.0.12/30", "255.0.0.16/32"],
but our answer was the shortest possible.

Also note that a representation beginning with say, "255.0.0.7/30" would be incorrect,
because it includes addresses like 255.0.0.4 = 11111111 00000000 00000000 00000100 
that are outside the specified range.

Note:

1. ipwill be a valid IPv4 address.
2. Every implied addressip + x(forx < n) will be a valid IPv4 address.
3. nwill be an integer in the range[1, 1000] .

这道题是Airbnb必面的一道题，不出现在电话面试就出现在onsite。所以还是有必要研究明白的。

IP address:

https://en.wikipedia.org/wiki/IP_address

https://zh.wikipedia.org/wiki/网际协议

CIDR:

https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing

https://zh.wikipedia.org/wiki/无类别域间路由

首先先要有把ip地址转成long的method，以及把long转成ip地址的method

思路：对于起始的ip（start），首先找到从右数第一个bit为1d的位置，这时候我们知道了有多少trailing 0，有多少个bit可以用于CIDR的长度，这个长度可能大于需要表示的长度，也可能小于，所以我们还需要检查哪个长度更长，避免越界，具体细节就是取两个mask中较大的。不断更新start和剩下的需要表示的长度，直到start > end

class Solution {
    public List<String> ipToCIDR(String ip, int n) {
        List<String> res = new ArrayList<String>();
        long start = ipToLong(ip);
        long end = start + n - 1;

        while(start <= end) {
            long firstOne = start & (-start);
            int mask1 = 32 - (int) (Math.log(firstOne) / Math.log(2));

            int mask2 = 32 - (int) (Math.log(end - start + 1) / Math.log(2));
            mask1 = Math.max(mask1, mask2);
            String cidr = longToIp(start) + "/" + mask1;
            res.add(cidr);

            start += (int) Math.pow(2, 32 - mask1);
        }

        return res;
    }

    public long ipToLong(String ip) {
        String[] parts = ip.split("\\.");
        long res = 0;
        int offset = 0;

        for(int i = parts.length - 1; i >= 0; i--) {
            res += Integer.parseInt(parts[i]) << offset;
            offset += 8;
        }

        return res;
    }

    public String longToIp(long ip) {
        long mask = 0xFF;
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < 4; i++) {
            res.insert(0, ip & mask);
            if(i != 3)
                res.insert(0, ".");
            ip = ip >> 8;
        }

        return res.toString();
    }
}