空气床面经题ip2cidr C++实现

最近看版上空气床的面经，发现大家经常提到一个ip2cidr的题目，找不到代码，于是自己现实了一把，供大家讨论参考。

题目：给一个IP地址范围，比如"10.10.1.1" - "10.12.235.12"，转换成其CIDR表示。CIDR（classless inter-domain routing）的定义可以自行google，这题的主要意思就是转换成一系列的CIDR地址，刚好覆盖给出的IP地址范围（不多不少）。

算法：
从一个简单的例子开始：
比如IP地址范围是 0.0.0.111 - 0.0.0.120，对应的二进制表示如下
1101111   - 111
1110000   - 112
   ...
1110111   - 119
1111000   - 120

显然 0.0.0.(11000000)/24可以覆盖整个地址区间。但是这个CIDR不是一个“合格”的CIDR，因为它的范围太大了，超出了输入的IP地址范围，所以我们要进一步缩小。

缩小的办法是把这个最大的CIDR对半分得到两个CIDR：
- 0.0.0.(11000000)/24
- 0.0.0.(11100000)/25
我们可以把输入的IP地址范围分到这两个CIDR中去，然后再递归求解，直到CIDR恰好覆盖IP区间，则得到合格的CIDR。

具体代码

1. 
   
2. uint32_t IpToInt(string &ip) {
   
3.         vector<string> segments;
   
4.         boost::split(segments, ip, [](char ch) {return ch == '.'; });
   
5.         uint32_t res = 0;
   
6.         uint32_t mul = 1;
   
7.         for (int i = 0; i < segments.size(); ++i) {
   
8.                 res = res << 8; //every time left shift 8 bits
   
9.                 res += boost::lexical_cast<uint32_t>(segments[i]);
   
10.         }
    
11.         return res;
    
12. }
    
13. 
    
14. string IntToIp(uint32_t ip) {
    
15.         string res;
    
16.         for (int i = 0; i < 4; ++i) {
    
17.                 uint32_t mod = ip % 256;
    
18.                 res = to_string(mod) + (i != 0 ? ".": "") + res;
    
19.                 ip = ip >> 8;
    
20.         }
    
21.         return res;
    
22. }
    
23. 
    
24. void helper(uint32_t start, uint32_t end, uint32_t prefix, int prefix_length, vector<string> &ans) {
    
25.         uint32_t range_start = prefix;
    
26.         uint32_t range_end = prefix + ((uint64_t)1 << (32 - prefix_length)) - 1;
    
27.         if (start == range_start && end == range_end) {
    
28.                 string cidr;
    
29.                 cidr = IntToIp(prefix);
    
30.                 cidr.append("/");
    
31.                 cidr.append(to_string(prefix_length));
    
32.                 ans.push_back(cidr);
    
33.                 return;
    
34.         }
    
35.         uint32_t prefix_1 = prefix + (1 << (31 - prefix_length));
    
36.         if (end < prefix_1) {
    
37.                 helper(start, end, prefix, prefix_length + 1, ans);
    
38.         }
    
39.         else if(start >= prefix_1){
    
40.                 helper(start, end, prefix_1, prefix_length + 1, ans);
    
41.         }
    
42.         else {
    
43.                 helper(start, prefix_1 - 1, prefix, prefix_length + 1, ans);
    
44.                 helper(prefix_1, end, prefix_1, prefix_length + 1, ans);
    
45.         }
    
46. }
    
47. 
    
48. void IpToCidr(string start_ip, string end_ip, vector<string> &ans) {
    
49.         uint32_t start = IpToInt(start_ip);
    
50.         uint32_t end = IpToInt(end_ip);
    
51.         int prefix_length = 0;
    
52.         while (prefix_length <= 31) {
    
53.                 uint32_t mask = 1 << (31 - prefix_length);
    
54.                 if (mask & end) {
    
55.                         break;
    
56.                 }
    
57.                 else {
    
58.                         ++prefix_length;
    
59.                 }
    
60.         }
    
61.         helper(start, end, 0, prefix_length, ans);
    
62. }

复制代码

这种题目用递归有点杀鸡牛刀哈。

#include <string>
#include <cstdint>
#include <iostream>

using namespace std;

class Solution {
public:
   void cidr(const string& start_ip, const string& end_ip, vector<string>& result) {
        uint32_t start = aton(start_ip), end = aton(end_ip);
        while (start <= end) {
            uint32_t val = lsb(start);
            val = std::min(val, end - start + 1);
            int pos = indexOf(val);
            int mask = 32 - pos;
            result.push_back(ntoa(start) + "/" + std::to_string(mask));
            start += 1 << pos;
        }
    }
private:
    static constexpr int N = 4;
private:
    uint32_t aton(const string& ip) {
        uint32_t result = 0, val = 0;
        int n = ip.size();
        for (int i = 0; i <= n; ++i) {
            if (i == n || ip[i] == '.') {
                result = (result << 8) + val;
                val = 0;
            } else {
                val = 10 * val + ip[i] - '0';
            }
        }
        return result;  
    }
   
    string ntoa(uint32_t ip) {
        string s;
        for (int i = N - 1; i >= 0; --i) {
            s  = (i != 0 ? "." : "") + std::to_string(ip % 256) + s;
            ip >>= 8;
        }
        return s;
    }
   
    int indexOf(uint32_t num) {
        int count = 0;
        for (/*NOOP*/; num != 1; num >>= 1) {
            count++;
        }
        return count;
    }
   
    uint32_t msb(uint32_t num) {
        uint32_t mask = 1U << 31;
        while (! num & mask) {
            mask >>= 1;
        }
        return mask;
    }
   
    uint32_t lsb(uint32_t num) {
        return num & (-num);
    }
};

int main() {
    vector<string> result;
    Solution sol;
    sol.cidr("10.5.2.10", "10.5.2.209", result);
    for (auto& c : result) {
        cout << c << " ";
    }
    return 0;
}

自己顶一下，发现当年用C++刷题简直太实诚了

这题最好是用位运算，包括__builtin_clz和__bulitin_ctz函数的使用，这两条指令在x86架构的处理器上一般都有硬件实现。

很多情况下，__builtin_ctz（Count Trailing Zeros）的功能可以用x & -x这样的写法替代。

参考这里：http://www.cnblogs.com/grandyang/p/8440087.html

上面的代码也还不是最优的，因为有个内while循环：while (step > n) step /= 2;
这个循环本质上是要找n最高位1，可以用__builtin_clz改写。

和 乐扣七五一 是一样的原题吧？？

southriver 发表于 2018-7-9 05:47
自己顶一下，发现当年用C++刷题简直太实诚了

哈哈哈哈为什么这么说？求详解！

谢谢分享！有收获！