IP to CIDR

BitOperation

Easy? At least Medium...

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.

Example 1:

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 address ip + x(for x < n) will be a valid IPv4 address.

3. nwill be an integer in the range [1, 1000].

Analysis & Solution

Bit operation.

https://leetcode.com/problems/ip-to-cidr/discuss/151348/Java-Solution-with-Very-Detailed-Explanation-8ms

1. Convert the IP string into an Integer

2. Greedily take the biggest block of IP Addresses at each step

3. At each step convert back into String Form

https://leetcode.com/problems/ip-to-cidr/discuss/110222/Very-Simple-Java-Solution-(beat-100

找当前ip区间剩余可用range，有两种思路，一种是找 numberOfTrailingZeros, 一种是找 lowestOneBit

Integer.numberOfTrailingZeros(x)
Integer.lowestOneBit(x)

区别在于一个是找0，一个是找1。

除了lowestOneBit(), 还可以用bit 运算：

x & -x

用lowestOneBit找1的时候，需要对0.0.0.0的情况特殊处理，

if (step == 0) {
    step = 1024;
}

然后再greedy地移动step，直到step > n的条件不满足；此时step代表了可以共享leading bits的区间的最小值的最末几位，在convertToIP中，再得到相应的共享leading bits的长度。

需要注意的是 step 是 lowestOneBit，因此如果末尾是这种形式: xxxxx100, 那么step = 4，而共享的prefix bit要包含100中的这个1, 因此 len = 32 + 1; 因为我们需要的是32 - (末尾0的个数) = 32 - (number of bits in step - 1)，才是prefix bits的长度。

int len = 33;
while (step > 0) {
    len--;
    step >>= 1;
}

代码：

class Solution {
    public List<String> ipToCIDR(String ip, int n) {
        List<String> ans = new ArrayList<String>(); 
        long x = convertIPtoLong(ip);

        while (n > 0) {
            long step = Long.lowestOneBit(x);
            if (step == 0) {
                step = 1024;
            }
            while (step > n) {
                step >>= 1;
            }
            ans.add(convertToIP(x, (int) step));
            x += step;
            n -= step;
        }
        return ans;
    }

    // Convert IP to Long like base 256
    public long convertIPtoLong(String ip) {
        long x = 0;
        String[] sps = ip.split("\\.");
        for (String sp: sps) {
            x *= 256;
            x += Integer.parseInt(sp);
        }
        return x;
    }

    // Convert IP and range to CIDR
    private String convertToIP(long x, int step) {
        int[] ip = new int[4];
        for (int i = 0; i < 3; i++) {
            ip[i] = (int) (x & 255);
            x >>= 8;
        }
        ip[3] = (int) x;

        // Shared prefix bits length
        // step includes 1 bit of the shared prefix, thus 32 + 1
        int len = 33;
        while (step > 0) {
            len--;
            step >>= 1;
        }
        return ip[3] + "." + ip[2] + "." + ip[1] + "." + ip[0] + "/" + len;
    }
}

Reference

https://leetcode.com/problems/ip-to-cidr/discuss/151348/Java-Solution-with-Very-Detailed-Explanation-8ms

https://leetcode.com/problems/ip-to-cidr/discuss/110222/Very-Simple-Java-Solution-(beat-100\

http://www.cnblogs.com/grandyang/p/8440087.html