T793074 【C1155】 - IP网络

Alex是一个IP网络管理员。他的客户拥有许多个独立的IP地址，他决定将这些IP地址归并到尽可能小的IP网络中。 每个IP地址是一个4字节的数字，按字节以点分十进制表示法写成：`“byte0.byte1.byte2.byte3”`（引号用于说明）。每个字节表示为0到255（包括0和255）的十进制数，且没有多余的前导零。 IP网络由两个4字节的数字描述——网络地址（network address）和网络掩码（network mask）。网络地址和网络掩码的表示方法与IP地址相同。 为了理解网络地址和网络掩码的意义，需要考虑它们的二进制表示。IP地址、网络地址和网络掩码的二进制表示由32位组成： - **byte0** 的8位（二进制从高到低排列） - 接着是 **byte1** 的8位 - 再接着是 **byte2** 的8位 - 最后是 **byte3** 的8位。 一个IP网络包含了 $2^n$ 个IP地址，其中 $0 \leq n \leq 32$。 - **网络掩码** 在二进制表示中总是从高位开始的 $32 - n$ 位设置为1，低位的 $n$ 位设置为0。 - **网络地址** 的二进制表示中前 $32 - n$ 位是任意值，后 $n$位设置为0。 一个IP网络包含所有与网络地址的前 $32 - n$ 位相同、后 $n$位任意的IP地址。如果一个IP网络包含的IP地址数量少于另一个网络，则我们认为前者的网络“更小”。 例如： 网络地址为 `194.85.160.176`，网络掩码为 `255.255.255.248` 的IP网络包含从 `194.85.160.176` 到 `194.85.160.183` 共8个IP地址（包含端点）。

输入文件包含多个测试用例，每个测试用例的格式如下： - 第一行是一个整数 $m$ ($1 \leq m \leq 1000$)，表示有 $m$ 个IP地址。 - 接下来的 $m$ 行中，每行一个IP地址。每个IP地址可能在输入文件中出现多次。

对于每个测试用例，输出两行描述包含所有输入IP地址的最小可能的IP网络： - 第一行是网络地址 - 第二行是网络掩码

### 补充说明 输入会有多组测试数据，最后以EOF作为输入结束的标志 IP网络地址为 `194.85.160.176`，网络掩码为 `255.255.255.248` 的IP网络包含从 `194.85.160.176` 到 `194.85.160.183` 共8个IP地址（包含端点）。 IP网络地址为 `194.85.160.176`的二进制表示为： `11000010 . 01010101 . 10100000 . 10110000` 网络掩码为 `255.255.255.248`的二进制表示为：`11111111 . 11111111 . 11111111 . 11111000` 网络地址通过将IP地址与网络掩码按位与（AND）运算得到：`11000010 . 01010101 . 10100000 . 10110000` => `194.85.160.176` 在这个子网中，主机地址范围是从网络地址到广播地址之间的地址（包含网络地址和广播地址）： - 网络地址的主机部分：末尾的`000` 到 `111`，共8个IP地址，由掩码的最后的3个0控制 - 可用主机地址范围：`194.85.160.176` - `194.85.160.183` 可以简单的认为网络掩码的前n位的1用于确定的是网络地址，后m位的0用于确定网络主机的地址（n + m = 32位） 如果末尾有m位0，则可以有`0000..`（m位） - `111..`（m位）的主机地址 网络掩码的作用也可以认为是掩饰掉网络IP中的不同的信息（主机部分），将这部分置为0，保留相同的信息（网络部分），将这部分置为1 #### 如何计算多个不同IP的网络掩码 计算多个不同IP地址的网络掩码的过程是为了找到它们的**公共网络前缀**，也就是确定这些IP地址属于同一个网络的最小网络掩码。以下是详细步骤： --- **步骤 1：将IP地址转换为二进制** 将每个IP地址转换为32位二进制表示。例如： - **IP1**: `192.168.1.1` → `11000000.10101000.00000001.00000001` - **IP2**: `192.168.1.5` → `11000000.10101000.00000001.00000101` --- **步骤 2：比较每位，找出公共前缀** 从左到右比较每一位二进制数： - 如果相同，保留该位；对应的网络掩码设置为1 - 如果不同，从此位置开始就没有公共前缀了。从第1个不同位开始到最后，网络掩码设置为0 ### 网络知识补充阅读（选读） #### IP地址和网络掩码 **IP地址**和**网络掩码**是计算机网络中非常重要的概念，用于标识设备并划分网络。 IP地址是分配给网络设备的唯一标识，用于在网络中标识一个设备的位置。 - IPv4地址由四组十进制数字组成，每组数字的范围是`0-255`，用点分隔，例如：`192.168.1.1`。 - 每个IPv4地址由**网络部分**和**主机部分**组成： - **网络部分**：标识设备所在的网络。 - **主机部分**：标识该网络中的具体设备。 网络掩码（Subnet Mask）用于划分网络和主机的范围，帮助确定IP地址的**网络部分**和**主机部分**。 - IPv4网络掩码通常用`点分十进制`表示，例如：`255.255.255.0`。 - 每个网络掩码的作用是： - **1**表示网络部分。 - **0**表示主机部分。 假设IP地址为`192.168.1.1`，网络掩码为`255.255.255.0`： - 网络部分是`192.168.1`（由掩码的1决定）。 - 主机部分是`.1`（由掩码的0决定）。 IP地址和网络掩码结合可以确定设备所在的网络。例如： - **IP地址**：`192.168.1.1` - **网络掩码**：`255.255.255.0` 计算得到的网络地址是`192.168.1.0`，表示这个设备属于`192.168.1.0/24`的网络。 用斜杠表示网络掩码中连续的1的数量。例如： - `255.255.255.0`可以写作`/24`。 - `255.255.0.0`可以写作`/16`。 #### 网络掩码的作用 网络掩码的主要作用是**划分网络**，帮助区分IP地址中的**网络部分**和**主机部分**，从而实现高效的网络管理和通信。 网络掩码通过将IP地址的某些位固定为网络部分，可以确定一个网络的范围。例如： - **IP地址**：`192.168.1.1` - **网络掩码**：`255.255.255.0` - IP地址的前24位由掩码的`1`表示为网络部分，结果是：`192.168.1.0/24`。 - **网络范围**：`192.168.1.0`到`192.168.1.255`。 设备通信前需要判断是否在同一网络： 1. 将两台设备的IP地址分别与其网络掩码按位与（AND）运算。 2. 如果结果相同，说明它们在同一网络中，可以直接通信；否则需要通过网关通信。 比如： - **设备A**：IP地址`192.168.1.1`，掩码`255.255.255.0`。 - **设备B**：IP地址`192.168.1.100`，掩码`255.255.255.0`。 计算网络地址： - `192.168.1.1 & 255.255.255.0 = 192.168.1.0` - `192.168.1.100 & 255.255.255.0 = 192.168.1.0` 结果相同，说明两台设备在同一网络中。