题解 | #判断两个IP是否属于同一子网#

# include <iostream>
# include <string>
# include <vector>
# include <sstream>
# include <cmath>
using namespace std; 

// 用于分割地址中各段的字符串
vector<string> get_string(string s) {
    istringstream is(s);
    string seg;
    vector<string> res;
    while (getline(is, seg, '.')) {
        res.push_back(seg);
    }
    return res;
}

// 判断IP地址是否合法
bool judge_IP(string s) {
    vector<string> IP = get_string(s);
    int k = 0;
    for (vector<string>::iterator iter = IP.begin(); iter != IP.end(); iter++) {
        auto seg = *iter;
        k++;
        if (seg == " ") return false;
        else {
            if (stoi(seg) > 255) return false;
            if (stoi(seg) < 0) return false;
        }
    }
    if (k == 4) return true;
    else return false;
}

// 判断子网掩码地址是否合法
bool judge_mask(string s) {
    vector<string> mask = get_string(s);
    unsigned b = 0;
    for (vector<string>::iterator iter = mask.begin(); iter != mask.end(); iter++) {
        auto seg = *iter;
        if (seg == " ") return false;
        else {
            // 将子网掩码地址转换为32位无符号整形
            b = (b << 8) + stoi(seg);
        }
    }
    if (!b) {
        return false;  // b为零，非法
    }
    b = ~b + 1;
    if (b == 1) {
        return false;  // b按位取反后加一，如果此时b为1，则b原来是二进制全一，非法
    }
    if ((b & (b - 1)) == 0) {
        return true;  // b和b-1按位运算后为0，合法
    }
    return false;
}

// 将十进制转换为二进制
vector<string> dec_bin(vector<string> dec) {
    vector<string> res;
    for (vector<string>::iterator iter = dec.begin(); iter != dec.end(); iter++) {
        int val = stoi(*iter);
        string s;
        int rem = val % 2;
        val /= 2;
        s = s + to_string(rem);
        while (val != 0) {
            rem = val % 2;
            val /= 2;
            s = s + to_string(rem);
        }
        string s_reverse;
        if (s.size() != 8) {
            // 不足8位
            int num = 8 - s.size();
            for (int k = 0; k < num; k++) {
                s_reverse = s_reverse + "0";
            }
        }
        for (int j = s.size() - 1; j >= 0; j--) {
            s_reverse = s_reverse + s[j];
        }
        res.push_back(s_reverse);
    }
    return res;
}

//将二进制转换为十进制
vector<int> bin_dec(vector<string> s) {
    vector<int> dec;
    int sum = 0;
    for (vector<string>::iterator iter = s.begin(); iter != s.end(); iter++) {
        string temp = *iter;
        for(int i = temp.size() - 1; i >= 0; i--) {
            sum += stoi(string(1, temp[i])) * pow(2, temp.size() - 1 - i);
        }
        dec.push_back(sum);
        sum = 0;
    }
    return dec;
}

// 判断两个IP地址是否在同一个子网中
bool judge_IP_isSame(string mask, string IP1, string IP2) {
    vector<string> v_mask_temp = get_string(mask);
    vector<string> v_IP1_temp = get_string(IP1);
    vector<string> v_IP2_temp = get_string(IP2);
    // 将十进制转换为二进制
    vector<string> v_mask = dec_bin(v_mask_temp);
    vector<string> v_IP1 = dec_bin(v_IP1_temp);
    vector<string> v_IP2 = dec_bin(v_IP2_temp);
    // 合成二进制
    string mask_bin, IP1_bin, IP2_bin;
    for (int i = 0; i < 4; i++) {
        mask_bin = mask_bin + v_mask[i];
        IP1_bin = IP1_bin + v_IP1[i];
        IP2_bin = IP2_bin + v_IP2[i];
    }
    // 两个二进制取与操作
    string AND1, AND2;
    for (int i = 0; i < 32; i++) {
        if (mask_bin[i] == '1' && IP1_bin[i] == '1') AND1 = AND1 + "1";
        else AND1 = AND1 + "0";
        if (mask_bin[i] == '1' && IP2_bin[i] == '1') AND2 = AND2 + "1";
        else AND2 = AND2 + "0";
    }
    // 拆分为四段字符串
    vector<string> AND1_seg, AND2_seg;
    for (int i = 0; i < 4; i++) {
        AND1_seg.push_back(AND1.substr(i * 8, 8));
        AND2_seg.push_back(AND2.substr(i * 8, 8));
    }
    // 二进制转换为十进制（这一步其实不用转换，直接比较二进制就可以了）
    vector<int> AND1_dec, AND2_dec;
    AND1_dec = bin_dec(AND1_seg);
    AND2_dec = bin_dec(AND2_seg);
    // 判断是否相等
    for (int i = 0; i < 4; i++) {
        if (AND1_dec[i] != AND2_dec[i]) return false;
    }
    return true;
}


int main(){
    string mask, IP1, IP2;
    getline(cin, mask, '\n');
    getline(cin, IP1, '\n');
    getline(cin, IP2, '\n');
    // 判断地址是否非法
    if (!judge_mask(mask) || !judge_IP(IP1) || !judge_IP(IP2)) {
        cout << "1" << endl;
    } else {
        if (judge_IP_isSame(mask, IP1, IP2)) {
            // 两个IP属于同一个网络
            cout << "0" << endl;
        } else {
            // 两个IP不属于同一个网络
            cout << "2" << endl;
        }
    }
    return 0;
}