LeetCode 751. IP 到 CIDR（贪心）

示例 1：
输入：ip = "255.0.0.7", n = 10
输出：["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]
解释：
转换为二进制时，初始IP地址如下所示（为清晰起见添加了空格）：
255.0.0.7 -> 11111111 00000000 00000000 00000111
地址 "255.0.0.7/32" 表示与给定地址有相同的 32 位前缀的所有地址，
在这里只有这一个地址。

地址 "255.0.0.8/29" 表示与给定地址有相同的 29 位前缀的所有地址：
255.0.0.8 -> 11111111 00000000 00000000 00001000
有相同的 29 位前缀的地址如下：
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

地址 "255.0.0.16/32" 表示与给定地址有相同的 32 位前缀的所有地址，
这里只有 11111111 00000000 00000000 00010000。

总之，答案指定了从 255.0.0.7 开始的 10 个 IP 的范围。

有一些其他的表示方法，例如：
["255.0.0.7/32","255.0.0.8/30", "255.0.0.12/30", "255.0.0.16/32"],
但是我们的答案是最短可能的答案。

另外请注意以 "255.0.0.7/30" 开始的表示不正确，
因为其包括了 255.0.0.4 = 11111111 00000000 00000000 00000100 这样的地址，
超出了需要表示的范围。
 
注：
ip 是有效的 IPv4 地址。
每一个隐含地址 ip + x (其中 x < n) 都是有效的 IPv4 地址。
n 为整数，范围为 [1, 1000]。

class Solution {
public:
    vector<string> ipToCIDR(string ip, int n) {
    	long init = iptolong(ip);//转化成256进制的4位数
    	vector<string> ans;
    	while(n)
    	{
    		int tail0 = tail0count(init);//该数后面有多少个尾0
    		long mask = 0, numofips = 1;
    		while(numofips < n && mask < tail0)
    		{	//该数后面都可以容纳多少个 ip
    			numofips <<= 1;
    			mask++;
    		}
    		if(numofips > n)
    		{	//超了，要减回去
    			numofips >>= 1;
    			mask--;
    		}
    		ans.push_back(iptostr(init, 32-mask));
    		n -= numofips;//还剩余多少
    		init += numofips;//ip开始位置更新
    	}
    	return ans;
    }
    long iptolong(string& ip)
    {	//ip转256进制数
    	vector<int> num;
    	long n = 0, i;
    	for(i = 0; i < ip.size(); ++i)
    	{
    		if(ip[i] == '.')
    		{
    			num.push_back(n);
    			n = 0;
    		}
    		else
    		{
    			n = 10*n+ip[i]-'0';
    			if(i == ip.size()-1)
    				num.push_back(n);
    		}
    	}
    	n = 0;
    	for(i = 0; i < 4; ++i)
    		n = n*256+num[i];
    	return n;
    }
    string iptostr(long n, int range)
    {	//ip+range
    	string ip;
    	vector<int> num;
    	while(n)
    	{
    		num.push_back(n%256);
    		n /= 256;
    	}
        while(num.size() < 4)
            num.push_back(0);
    	ip = to_string(num[3])+'.'+to_string(num[2])+'.'
    		+to_string(num[1])+'.'+to_string(num[0])+'/'+to_string(range);
    	return ip;
    }
    int tail0count(long n)
    {
    	int count = 0, i = 0;
        if(n == 0)
            return 0;
    	while(((n>>i)&1)==0)
    	{
    		count++;
    		i++;
    	}
    	return count;
    }
};