C# 位运算实战：把任意 IP 段拆成最少的 CIDR 块

在网络工程里，有一个很常见的小问题：给你一个 IP 段（比如 10.0.0.5 ~ 10.0.0.250），让你把它拆成最少的 CIDR 块。听起来简单，做起来并不轻松——尤其是当这个 IP 段不是从边界开始、也不是以 2 的整数次幂结尾的时候。

最近在 SwitchData 项目里做 UPF（User Plane Function，用户面功能）地址分配模块，正好遇到了这个需求：业务方给我们一个起始 IP 和结束 IP，我们要把它转成若干个 CIDR，然后才能写到路由表里。看起来像是一道”面试题”，但真要写出一个通用、正确、高效、还同时支持 IPv4 和 IPv6 的实现，就不那么容易了。

这篇文章就把这个问题的解法完整地拆开讲一遍：核心是 位运算 + UInt128。

一、为什么需要拆分 CIDR？

CIDR（Classless Inter-Domain Routing，无类域间路由）用 IP/掩码 的形式表示一个 IP 段，比如：

10.0.0.0/24   表示 10.0.0.0 ~ 10.0.0.255（共 256 个地址）
10.0.0.0/26   表示 10.0.0.0 ~ 10.0.0.63 （共 64 个地址）

CIDR 的特点是长度必须是 2 的整数次幂，且起始地址必须按块大小对齐。

但现实中，业务给的地址段很少这么”规整”：

起始 IP	结束 IP	是不是一个 CIDR？
10.0.0.0	10.0.0.255	✅ 就是 10.0.0.0/24
10.0.0.5	10.0.0.250	❌ 必须拆成多个
192.168.1.0	192.168.2.127	❌ 必须拆成多个

对于第二种情况，我们的目标就是用最少的 CIDR 把整个区间覆盖掉。

二、思路：从大块开始贪心

先别想算法，来看个直观的例子。把 10.0.0.5 ~ 10.0.0.20 拆 CIDR：

区间: 10.0.0.5 ................. 10.0.0.20

最大能覆盖的 CIDR（从 10.0.0.5 开始）：
10.0.0.5/32   → 只有 10.0.0.5 一个，太碎

正确的写法是：

每一步都找”以当前起点为基址的最大 CIDR”，然后从区间中”挖掉”它，继续处理剩下的部分。

这就是典型的贪心算法：

算出当前起点 start 最多能”承载”多大的 CIDR（受两个因素限制：① start 自己的对齐位；② 不能超过终点 end）。
把这个 CIDR 加入结果。
把 start 推进到该 CIDR 之后的第一个地址。
重复直到 start > end。

唯一的关键就是第 1 步：怎么算”以 start 为基址的最大 CIDR”？

三、关键：CountTrailingZeros

假设 start 是一个 128 位无符号整数（IPv4 视为高 96 位为 0 的 UInt128），那么：

start 的末尾连续 0 的个数记为 z。
start 能作为 CIDR 基址的最大前缀长度 = 总位数 − z。

举例（IPv4 总位数为 32）：

start = 10.0.0.0  → 二进制 ... 0000  → 末尾 0 个数 = 0
                  → 最多前缀 32 - 0 = 32，即 10.0.0.0/32（只有它自己一个）

start = 10.0.0.4  → 二进制 ... 0100  → 末尾 0 个数 = 2
                  → 最多前缀 32 - 2 = 30，即 10.0.0.4/30（4 个地址）

start = 10.0.0.8  → 二进制 ... 1000  → 末尾 0 个数 = 3
                  → 最多前缀 32 - 3 = 29，即 10.0.0.8/29（8 个地址）

直觉上也好理解：末尾有几个 0，就说明它已经被 2^z 对齐了。比如末三位 0 就是 8 对齐，那它至少可以是 /29（每块 8 个）。

四、UInt128 的妙用

IPv4 用 uint（32 位）就够了，但 IPv6 有 128 位。.NET 早期没有原生的 128 位整数，只能用 BigInteger，但 BigInteger 的位运算比原生长度慢得多。

.NET 7+ 起内置了 UInt128，所有位运算、移位、比较、加减全都是原生指令，性能和 uint 几乎一样。于是我们可以把 IPv4 和 IPv6 用同一套代码搞定。

把任意 IPAddress 转成 UInt128：

public static UInt128 IPAddressToUInt128(IPAddress ip)
{
    byte[] bytes = ip.GetAddressBytes();
    UInt128 value = 0;
    for (int i = 0; i < bytes.Length; i++)
    {
        value = (value << 8) | bytes[i];
    }
    return value;
}

把 UInt128 转回 IPAddress（按地址族决定是 4 字节还是 16 字节）：

public static byte[] UInt128ToBytes(UInt128 value, AddressFamily family)
{
    int length = family == AddressFamily.InterNetwork ? 4 : 16;
    byte[] bytes = new byte[length];
    for (int i = length - 1; i >= 0; i--)
    {
        bytes[i] = (byte)(value & 0xFF);
        value >>= 8;
    }
    return bytes;
}

五、CountTrailingZeros 的实现

.NET 没有现成的 UInt128.TrailingZeroCount()（它有 BitOperations.TrailingZeroCount，但只支持 uint/ulong），所以自己写一个：

/// <summary>
/// 计算 UInt128 整数末尾连续 0 的个数，最多不超过 addressBits。
/// </summary>
public static int CountTrailingZeros(UInt128 value, int addressBits)
{
    int trailingZeros = 0;
    while (trailingZeros < addressBits && (value & 1) == 0)
    {
        value >>= 1;
        trailingZeros++;
    }
    return trailingZeros;
}

性能小贴士：如果追求极致速度，可以把 value 拆成两个 ulong，先用 BitOperations.TrailingZeroCount 处理低位，必要时再处理高位。生产环境中如果 IP 段很大再做这种优化，一般写法已经足够快了。

六、RangeToCidrs：核心算法

把上面的思路拼起来，就是 RangeToCidrs(start, end, family)：

public static List<IPNetwork2> RangeToCidrs(
    UInt128 start, UInt128 end, AddressFamily addressFamily)
{
    if (start > end)
        throw new ArgumentException("起始 IP 地址必须小于或等于结束 IP 地址");

    int addressBits = GetAddressBits(addressFamily);   // IPv4=32, IPv6=128
    var results = new List<IPNetwork2>();

    while (start <= end)
    {
        // 1) 当前起点能承载的最大 CIDR 前缀
        int trailingZeros = CountTrailingZeros(start, addressBits);
        int prefix = addressBits - trailingZeros;

        // 2) 再检查：这么大的块会不会超出 end？超出就缩小
        while (prefix < addressBits)
        {
            int hostBits = addressBits - prefix;
            UInt128 blockSize = (hostBits == 128)
                ? UInt128.MaxValue
                : ((UInt128.One << hostBits) - 1);
            if (start + blockSize > end)
                prefix++;
            else
                break;
        }

        results.Add(new IPNetwork2(UInt128ToIPAddress(start, addressFamily), (byte)prefix));

        // 3) 推进到这块 CIDR 之后
        if (prefix == 0) break;   // 整个地址空间
        start += UInt128.One << (addressBits - prefix);
    }

    return results;
}

外层重载可以让我们直接传 IPAddress 或字符串，使用更友好：

public static List<IPNetwork2> RangeToCidrs(IPAddress start, IPAddress end)
    => RangeToCidrs(start.GetAddressBytes(), end.GetAddressBytes());

public static List<IPNetwork2> RangeToCidrs(string start, string end)
    => RangeToCidrs(IPAddress.Parse(start), IPAddress.Parse(end));

七、再来一个：单个 CIDR 判定

有时候我们想确认一个区间”是不是恰好一个 CIDR”。比如 10.0.0.0 ~ 10.0.0.255 是 /24，但 10.0.0.5 ~ 10.0.0.250 就不是。

判断逻辑：

区间大小 = end - start + 1，必须恰好是 2 的整数次幂（即二进制只有一个 1）。
start 的末尾 0 的个数必须不少于”区间大小的幂次”。

public static IPNetwork2 RangeToCidr(UInt128 start, UInt128 end, AddressFamily family)
{
    if (start > end)
        throw new ArgumentException("起始 IP 地址必须小于或等于结束 IP 地址");

    int addressBits = GetAddressBits(family);

    if (start == end)
        return new IPNetwork2(UInt128ToIPAddress(start, family), (byte)addressBits);

    UInt128 maxValue = (family == AddressFamily.InterNetworkV6)
        ? UInt128.MaxValue : uint.MaxValue;
    if (start == 0 && end == maxValue)
        return new IPNetwork2(UInt128ToIPAddress(start, family), 0);

    UInt128 blockSize = end - start + 1;
    if ((blockSize & (blockSize - 1)) != 0)       // 不是 2 的整数次幂
        throw new ArgumentException("无法用单个 CIDR 表示该 IP 地址范围");

    int hostBits = CountTrailingZeros(blockSize);
    int trailingZeros = CountTrailingZeros(start, addressBits);
    if (trailingZeros < hostBits)
        throw new ArgumentException("无法用单个 CIDR 表示该 IP 地址范围");

    int prefix = addressBits - hostBits;
    return new IPNetwork2(UInt128ToIPAddress(start, family), (byte)prefix);
}

(blockSize & (blockSize - 1)) != 0 是经典的”判断 2 的幂”位运算技巧，建议记住。

八、流程图

flowchart TD
    A[输入 start, end, family] --> B{start <= end?}
    B -- 否 --> X[抛异常]
    B -- 是 --> C[计算 addressBits]
    C --> D[循环: start <= end]
    D --> E[start 末尾连续 0 的个数 z]
    E --> F[初步 prefix = bits - z]
    F --> G{start + blockSize > end?}
    G -- 是 --> H[prefix++ 缩小块] --> G
    G -- 否 --> I[加入结果: start/prefix]
    I --> J{prefix == 0?}
    J -- 是 --> K[结束, 整个地址空间]
    J -- 否 --> L[start += 2 的 hostBits 次方] --> D
    K --> M[返回 CIDR 列表]
    D --> N{start > end?}
    N -- 是 --> M

九、跑几个测试

把 RangeToCidrs 接到 UPF 分配模块上跑几个真实场景：

输入: 10.0.0.0 ~ 10.0.0.255
输出: [10.0.0.0/24]                  ← 一个就够

输入: 10.0.0.5 ~ 10.0.0.20
输出: [10.0.0.5/32, 10.0.0.6/31,
      10.0.0.8/29, 10.0.0.16/30,
      10.0.0.20/32]                  ← 5 个 CIDR 覆盖 16 个地址

输入: 192.168.1.0 ~ 192.168.2.127
输出: [192.168.1.0/24, 192.168.2.0/25]

输入: 2001:db8:: ~ 2001:db8:0:ffff:ffff:ffff:ffff:ffff
输出: [2001:db8::/32]                ← IPv6 也正常工作

可以看到：结果数量最小、IPv4/IPv6 同套代码、纯位运算——这就是算法的力量。

十、为什么这个写法值得借鉴

把这个实现放到生产代码里，我比较看重的有三点：

统一抽象：用 UInt128 把 IPv4 和 IPv6 拉到同一个维度，业务层完全不用关心地址族。
纯位运算 + 简单循环：没有 IPAddress.Parse / TryParse 这种字符串解析的反复开销，性能稳定可预测。
可测性高：输入输出都是值类型（UInt128 和 AddressFamily），单元测试直接 Assert.Equal(expected, actual) 即可，不用拉网络。

在 UPF 地址分配场景里，它把”业务方给一段不规整的 IP 段”和”路由表只接受 CIDR 列表”这两个世界无缝连了起来。

十一、小结

把任意 IP 段拆成最少 CIDR，核心是三步：

贪心：每一步找当前起点能承载的最大 CIDR。
对齐判定：CountTrailingZeros(start) 决定 CIDR 的最大前缀。
UInt128 统一：.NET 7+ 用 UInt128 一套代码覆盖 IPv4 和 IPv6。

这个算法不大，但很经典，是位运算和数值类型结合的一个好范例。掌握了它，下次再遇到”地址段拆 CIDR”的需求，几十行代码就能搞定。

相关源码：SwitchData.Common/Net/IPHelper.cs 里的 RangeToCidrs / RangeToCidr / CountTrailingZeros，以及 SwitchData.Common/Net/NetHelper.cs 里实际调用这些方法做 UPF 地址段合并的实现。