Supernetting算法实现错误求助：生成结果不符合预期

你的函数返回0.0.0.0/24是因为两个核心逻辑错误：

1. 前缀长度计算错误：你取了所有子网中最大的前缀长度（24），但超网的前缀长度应该是所有子网网络地址的最长公共前缀长度，而非单个子网的最大前缀。
2. 公共前缀未匹配正确长度：你计算了所有网络地址的按位与，但没有根据这个结果推导对应的公共前缀长度，而是直接套用错误的前缀值。

错误逻辑拆解 #

测试用的子网包含10.x.x.x、172.16.x.x、192.x.x.x三类完全不重叠的地址段，它们的32位整数按位与结果是0（即0.0.0.0），对应的最长公共前缀长度是0，正确超网应为0.0.0.0/0。但你的函数错误地用了最大前缀长度24，导致输出0.0.0.0/24。

修复后的代码 #

QStringList IPSupernetting::calculateSupernet(const QStringList& subnets) {
    QList<quint32> networkAddresses;

    // 收集所有有效的子网网络地址（已应用掩码）
    for (const QString& subnet : subnets) {
        QStringList parts = subnet.split('/');
        if (parts.size() != 2) continue;

        QString networkStr = parts[0];
        bool ok;
        int prefixLength = parts[1].toInt(&ok);
        if (!ok || prefixLength < 0 || prefixLength > 32) continue;

        QHostAddress address(networkStr);
        if (address.isNull() || address.protocol() != QAbstractSocket::IPv4Protocol)
            continue;

        quint32 ipv4Addr = address.toIPv4Address();
        quint32 mask = 0xFFFFFFFF << (32 - prefixLength);
        // 确保得到正确的子网网络地址
        quint32 networkAddr = ipv4Addr & mask;
        networkAddresses.append(networkAddr);
    }

    if (networkAddresses.isEmpty()) {
        return {};
    }

    // 计算所有网络地址的公共前缀值
    quint32 commonPrefix = networkAddresses.first();
    for (quint32 addr : networkAddresses) {
        commonPrefix &= addr;
    }

    // 计算最长公共前缀的长度
    int prefixLength = 0;
    quint32 testMask = 0x80000000; // 从最高位开始检查
    while (testMask != 0) {
        bool allMatch = true;
        for (quint32 addr : networkAddresses) {
            if ((addr & testMask) != (commonPrefix & testMask)) {
                allMatch = false;
                break;
            }
        }
        if (!allMatch) {
            break;
        }
        prefixLength++;
        testMask >>= 1;
    }

    // 生成超网字符串
    QString supernet = QHostAddress(commonPrefix).toString() + "/" + QString::number(prefixLength);
    return {supernet};
}

修复说明 #

1. 收集有效网络地址：先过滤格式无效、协议不符的子网，将每个子网转换为掩码后的32位网络地址，确保后续计算的准确性。
2. 计算公共前缀值：通过按位与操作，得到所有子网网络地址的公共部分。
3. 推导前缀长度：从最高位开始逐位验证，统计所有子网都匹配的连续高位数量，得到最长公共前缀长度。
4. 生成正确结果：用公共前缀地址和计算出的前缀长度组合成最终超网。

测试结果 #

用你提供的测试子网列表，修复后的函数会返回0.0.0.0/0，这是覆盖所有给定子网的最小超网（因为这些子网分属不同的A/B类地址段，没有更短的公共前缀）。

内容的提问来源于stack exchange，提问作者Nizuko HattoRi