题解：UVA1590 IP网络 IP Networks
解决思路
1. 读取和转换数据
输入数据：
通常，输入数据是若干个 IP 地址，每个 IP 地址由 4 4 4 个字节（即 32 32 32 位）组成。
转换为二进制表示：
为了处理这些 IP 地址，我们需要将每个 IP 地址从点分十进制格式（如192.168.1.1）转换为 32 32 32 位的二进制字符串。转换步骤如下：
- 将每个 IP 地址的每个十进制段（如
192）转换为 8 8 8 位的二进制数（如11000000）。 - 将四个 8 8 8 位的二进制数连接成一个 32 32 32 位的二进制字符串（如
11000000101010000000000100000001）。
2. 找到公共前缀
公共前缀的概念：
公共前缀是所有 IP 地址的二进制表示中，从左开始连续相同的位数。这一部分表示了这些 IP 地址的共同网络部分。
找到公共前缀的步骤：
- 将所有 IP 地址的 32 32 32 位二进制字符串对齐。
- 从最左边开始逐位比较，直到遇到第一个不同的位为止。
- 记录相同的位数，这就是公共前缀的长度。
3. 确定网络掩码
计算网络掩码：
网络掩码是用来区分IP地址的网络部分和主机部分的。掩码的长度等于公共前缀的长度。网络掩码可以用 32 32 32 位的二进制数表示，其中前面是 1 1 1 ，后面是 0 0 0 。例如，如果公共前缀是 24 24 24 位，则网络掩码是11111111.11111111.11111111.00000000，即255.255.255.0 。
构造网络掩码：
- 将公共前缀的长度转换为掩码。例如，公共前缀长度是 24 24 24 位，则掩码是
255.255.255.0。 - 转换为点分十进制格式。
4. 构造最终输出
网络地址的计算：
网络地址是用公共前缀填充剩余的位数（即主机位）为 0 0 0 。例如，如果公共前缀是110000001010100000000001（前 24 24 24 位），剩下的 8 8 8 位为 0 0 0 ，则网络地址的二进制表示是11000000101010000000000100000000。将其转换为点分十进制格式，即得到网络地址（如192.168.1.0）。
输出结果：
- 输出网络地址。
- 输出网络掩码。
示例
假设有三个 IP 地址：192.168.1.1, 192.168.1.2, 和192.168.1.100。
转换为二进制：
192.168.1.1→11000000.10101000.00000001.00000001192.168.1.2→11000000.10101000.00000001.00000010192.168.1.100→11000000.10101000.00000001.01100100
公共前缀：
比较这三个二进制字符串，发现前 24 24 24 位是相同的。因此，公共前缀长度是 24 24 24 位。
网络掩码：
掩码是255.255.255.0。
网络地址：
将前 24 24 24 位作为网络地址，其余位填充 0 0 0 ，即192.168.1.0。
最终输出：
- 网络地址:
192.168.1.0 - 网络掩码:
255.255.255.0
就这样，即可解决这一问题了。
代码
//拒绝使用万能头!!!(doge)
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
// 定义一个32位无符号整型
typedef unsigned int uint32_t;
// 将IP地址由字符串转为32位二进制
uint32_t ipToBinary(const string &ip) {int a, b, c, d;uint32_t binaryIp;// 使用sscanf解析出IP的4个部分哦sscanf(ip.c_str(), "%d.%d.%d.%d", &a, &b, &c, &d);// 将4个部分组合成32位整型binaryIp = (a << 24) | (b << 16) | (c << 8) | d;return binaryIp;
}
// 将32位表示的IP转位字符串
string binaryToIp(uint32_t binaryIp) {char ip[16]; //IPv4最多15个字符（xxx.xxx.xxx.xxx）+null终止符sprintf(ip, "%u.%u.%u.%u", (binaryIp >> 24) & 0xFF, //F可以不大写(binaryIp >> 16) & 0xFF, (binaryIp >> 8) & 0xFF, binaryIp & 0xFF);return string(ip);
}
int main() {int m;cin >> m;vector<uint32_t> ips(m);// 读取所有IP并转为二进制for (int i = 0; i < m; ++i) {string ip;cin >> ip;ips[i] = ipToBinary(ip);}// 找到IP的公共前缀uint32_t mask = 0xFFFFFFFF;for (int i = 1; i < m; ++i) {mask &= ~(ips[0] ^ ips[i]);}// 计算掩码长度int n = 32;while (n > 0 && (mask & 0x80000000) == 0) {mask <<= 1;--n;}// 计算网络地址uint32_t networkAddress = ips[0] & mask;cout << binaryToIp(networkAddress) << "\n";习惯性"\n"cout << binaryToIp(mask) << "\n";return 0;
}
//完结撒花!!!