526互联

HJ39 判断两个IP是否属于同一子网

发布时间 2023-08-10 17:53:59作者: YURiCAhana

题目描述

IP地址是由4个0-255之间的整数构成的，用"."符号相连。
二进制的IP地址格式有32位，例如：10000011，01101011，00000011，00011000;每八位用十进制表示就是131.107.3.24
子网掩码是用来判断任意两台计算机的IP地址是否属于同一子网络的根据。
子网掩码与IP地址结构相同，是32位二进制数，由1和0组成，且1和0分别连续，其中网络号部分全为“1”和主机号部分全为“0”。
你可以简单的认为子网掩码是一串连续的1和一串连续的0拼接而成的32位二进制数，左边部分都是1，右边部分都是0。
利用子网掩码可以判断两台主机是否在同一子网中。
若两台主机的IP地址分别与它们的子网掩码进行逻辑“与”运算（按位与/AND）后的结果相同，则说明这两台主机在同一子网中。

示例：
I P 地址　 192.168.0.1
子网掩码　 255.255.255.0

转化为二进制进行运算：

I P 地址　 11000000.10101000.00000000.00000001
子网掩码　11111111.11111111.11111111.00000000

AND运算 11000000.10101000.00000000.00000000

转化为十进制后为：
192.168.0.0

I P 地址　 192.168.0.254
子网掩码　 255.255.255.0

转化为二进制进行运算：

I P 地址　11000000.10101000.00000000.11111110
子网掩码 11111111.11111111.11111111.00000000

AND运算 11000000.10101000.00000000.00000000

转化为十进制后为：
192.168.0.0

通过以上对两台计算机IP地址与子网掩码的AND运算后，我们可以看到它运算结果是一样的。均为192.168.0.0，所以这二台计算机可视为是同一子网络。

输入一个子网掩码以及两个ip地址，判断这两个ip地址是否是一个子网络。
若IP地址或子网掩码格式非法则输出1，若IP1与IP2属于同一子网络输出0，若IP1与IP2不属于同一子网络输出2。

注:
有效掩码与IP的性质为：

  1. 掩码与IP每一段在 0 - 255 之间
  2. 掩码的二进制字符串前缀为网络号，都由‘1’组成；后缀为主机号，都由'0'组成

输入描述：

3行输入，第1行是输入子网掩码、第2，3行是输入两个ip地址
题目的示例中给出了三组数据，但是在实际提交时，你的程序可以只处理一组数据（3行）。

输出描述：

若IP地址或子网掩码格式非法则输出1，若IP1与IP2属于同一子网络输出0，若IP1与IP2不属于同一子网络输出2

示例

输入：

255.255.255.0
192.168.224.256
192.168.10.4
255.0.0.0
193.194.202.15
232.43.7.59
255.255.255.0
192.168.0.254
192.168.0.1

输出：

1
2
0

说明：

对于第一个例子:
255.255.255.0
192.168.224.256
192.168.10.4
其中IP:192.168.224.256不合法，输出1

对于第二个例子:
255.0.0.0
193.194.202.15
232.43.7.59
2个与运算之后，不在同一个子网，输出2

对于第三个例子，2个与运算之后，如题目描述所示，在同一个子网，输出0

解题思路

先判断是否为合法ip和合法掩码，然后将两个ip和掩码分别做按位与操作判断是否在同一子网
判断是否为合法掩码：在是合法ip的前提下，将掩码的4个值按256进制转换成一个long int型的数mask，即对于一个型如x1.x2.x3.x4的掩码，mask以如下公式计算：

\[mask = x1 * 256^{3} + x2 * 256^{2} + x3 * 256^{1} + x4 * 256^{0} \]

若\((mask | (mask - 1)) == 0xFFFFFFFF\)，则为合法掩码

代码

vector<long> ipToVector(string ip){
    auto pos = ip.find('.');
    vector<long> res;
    long sum = 0;
    long mi = 3;
    while (pos != string::npos) {
        long num = static_cast<long>(stoi(ip.substr(0, pos)));
        if (num > 255 || num < 0){
            // 牛客的用例用存在负数的情况，要判断是否小于0
            // 如果此时有一个段不是合法ip直接返回当前的vector
            return res;
        }
        res.push_back(num);
        ip = ip.substr(pos + 1);
        pos = ip.find('.');
        sum += static_cast<long>(num * (pow(256, mi--)));
    }
    long num = static_cast<long>(stoi(ip));
    if (num > 255 || num < 0){
        // 如果最后一个段不合法，直接返回当前vector
        return res;
    }
    res.push_back(num);
    sum += static_cast<long>(num * (pow(256, mi))); // 把所有的合法ip均按公式转换成256进制的数，便于判断是否是合法掩码
    res.push_back(sum);
    return res;
}

// 判断是否为合法ip或掩码，当isMask为true时表示当前输入的ip为掩码
bool legalIp(const vector<long> & ip, bool isMask=false){
    // 判断是否为合法ip
    if (ip.size() != 5){
        // 由于在转换成vector的过程中，只要遇到不合法的段马上返回当前vector，所以若ip不合法，vector的size一定不为5
        return false;
    }

    return (!isMask) || ((ip[4] | (ip[4] - 1)) == 0xFFFFFFFF); // 若不是掩码直接为true，若是掩码需要进一步判断
}
int main() {
    string mask, ip1, ip2;
    while (cin >> mask >> ip1 >> ip2){
        vector<long> maskVec = ipToVector(mask);
        vector<long> ip1Vec = ipToVector(ip1);
        vector<long> ip2Vec = ipToVector(ip2);
        if (!legalIp(maskVec, true) || (!legalIp(ip1Vec)) || (!legalIp(ip2Vec))){
            cout << 1 << endl;
            continue;
        } else {
            int i = 0;
            for (i = 0; i < 4; ++i){
                if ((ip1[i] & mask[i]) != (ip2[i] & mask[i])){
                    cout << 2 << endl;
                    break;
                }
            }
            if (i == 4){
                cout << 0 << endl;
            }
        }

    }
    return 0;
}