POJ 2799 IP Networks：最小網絡範圍計算（公共前綴法）

問題描述

給定 m 個 IPv4 地址，找到包含所有地址的最小 CIDR 網絡（即最長公共前綴）。輸出網絡地址與子網掩碼。

核心原理

IPv4 地址為 32 位無符號整數。同一網絡下，所有地址的高位相同，低位任意。最小網絡對應所有地址的最長公共前綴。

• 網絡地址 = 所有地址按位與（保留公共前綴，低位置 0）。
• 子網掩碼 = 公共前綴長度為 1，其餘為 0。

算法：求最小值與最大值的公共前綴

對於無符號整數集合，其最長公共前綴等價於 min_val 和 max_val 的最長公共前綴。因為中間值的變化只會在低位。

步驟

1. 讀入所有 IP，轉為 uint32_t。
2. 求 min_ip 和 max_ip。
3. 從高位向低位找第一個不同位，位置 k（0-indexed 從高位）。公共前綴長 = k。
4. 掩碼 mask = ~((1u << (32-k)) - 1)（或 0xFFFFFFFF << (32-k)）。
5. 網絡地址 net = min_ip & mask。

完整代碼

#include 
#include 
#include 

uint32_t ip_to_int(int a, int b, int c, int d) {
    return (a << 24) | (b << 16) | (c << 8) | d;
}

void print_ip(uint32_t ip) {
    printf("%u.%u.%u.%u\n",
           (ip >> 24) & 0xFF,
           (ip >> 16) & 0xFF,
           (ip >> 8) & 0xFF,
           ip & 0xFF);
}

int main() {
    int m;
    while (scanf("%d", &m) == 1) {
        uint32_t min_ip = 0xFFFFFFFF, max_ip = 0;
        for (int i = 0; i < m; ++i) {
            int a, b, c, d;
            scanf("%d.%d.%d.%d", &a, &b, &c, &d);
            uint32_t ip = ip_to_int(a, b, c, d);
            min_ip = std::min(min_ip, ip);
            max_ip = std::max(max_ip, ip);
        }
        uint32_t diff = min_ip ^ max_ip;
        int prefix_len = 0;
        while (prefix_len < 32 && ((diff >> (31 - prefix_len)) & 1) == 0) ++prefix_len;
        uint32_t mask = (prefix_len == 0) ? 0 : (0xFFFFFFFFu << (32 - prefix_len));
        uint32_t net = min_ip & mask;
        print_ip(net);
        print_ip(mask);
    }
    return 0;
}

複雜度

• 時間 O(m)，單次掃描求 min/max。
• 空間 O(1)。

關鍵細節

• 使用 uint32_t 避免符號位擴展問題。
• 移位操作注意 1u 無符號字面量，防止溢出。
• prefix_len=0 時掩碼為 0，需特判避免 1u << 32 未定義行為。
• 輸出格式：點分十進制，無前導零。

總結

IP 網絡最小範圍問題本質是求一組 32 位整數的最長公共前綴。通過 min/max 異或快速定位首個不同位，構造掩碼與網絡地址，代碼簡潔高效，是網絡編程基礎功。