IPv4/IPv6正反迭代与CIDR：端点、规范化和溢出

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• IPv4四段0..255，标准十进制无前导零，start/end都包含；reverse决定−1或+1。
• CIDR接受host bits非零并规范化到网段；遍历全地址不是hosts()，/31和/32不能按传统广播规则删端点。IPv6用128位整数及标准ipaddress处理压缩文本，同样全范围含端点，不将/0实体化。

解题路线

1. 拼接octets为整数，next先检查越界再输出current，随后加step。到max输出一次后用Python大整数暂存max+1，下一次停止，不用32位wrap回0。
2. prefix p，size=2^(32−p)，low=(address//size)×size，high=low+size−1；forward low→high，reverse high→low。这是掩码等价表达，p0是全空间而非空。
3. IPv6Iterator使用IPv6Address/Network规范化，next检查边界后输出compressed文本，再increment。IPv4与IPv6不混在同一range；/128单地址，/0仅惰性前缀读取。惰性只保留current/end/step，不建list；/0有2^32次输出，生成器节省内存但不能消除时间。输入格式、CIDR斜线/前缀错误按合同拒绝。

手动走一遍

255.255.255.250正向输出6项，最后255.255.255.255不能漏。192.168.1.9/30规范化为192.168.1.8..11，全部4个；/32只有该IP。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def parse(address):
    parts=address.split('.')
    if len(parts)!=4 or any(not x.isascii() or not x.isdigit() or (len(x)>1 and x[0]=='0') for x in parts):raise ValueError("IPv4 text")
    numbers=list(map(int,parts))
    if any(x>255 for x in numbers):raise ValueError("octet")
    value=0
    for x in numbers:value=(value<<8)|x
    return value

def text(value):return '.'.join(str((value>>shift)&255) for shift in (24,16,8,0))
class Iterator:
    def __init__(self,start,reverse=False,end=None):
        self.current=parse(start);self.step=-1 if reverse else 1
        self.end=parse(end) if end is not None else (0 if reverse else 2**32-1)
    def __iter__(self):return self
    def __next__(self):
        if (self.current-self.end)*self.step>0:raise StopIteration
        value=self.current;self.current+=self.step;return text(value)
    @classmethod
    def cidr(cls,cidr,reverse=False):
        address,prefix=cidr.split('/');bits=int(prefix)
        if not 0<=bits<=32:raise ValueError("prefix")
        value=parse(address);size=1<<(32-bits);low=value//size*size;high=low+size-1
        return cls(text(high if reverse else low),reverse,text(low if reverse else high))

class IPv6Iterator:
    def __init__(self,address,reverse=False,end=None):
        from ipaddress import IPv6Address
        self.current=int(IPv6Address(address));self.step=-1 if reverse else 1
        self.end=int(IPv6Address(end)) if end is not None else (0 if reverse else 2**128-1)
    def __iter__(self):return self
    def __next__(self):
        from ipaddress import IPv6Address
        if (self.step>0 and self.current>self.end) or (self.step<0 and self.current<self.end):raise StopIteration
        output=str(IPv6Address(self.current));self.current+=self.step;return output
    @classmethod
    def cidr(cls,text,reverse=False):
        from ipaddress import IPv6Network
        network=IPv6Network(text,strict=False);low=network.network_address;high=network.broadcast_address
        return cls(str(high if reverse else low),reverse,str(low if reverse else high))

复杂度

固定IPv4地址每次O(1)位算术及常数长度格式化，迭代K项O(K)、状态O(1)。若扩展b位地址，解析/输出按b位成本另算。

易错点与追问

容易失分的边界

• 先increment再yield会漏起点。
• 使用hosts()会改变完整CIDR端点语义。

继续深挖

• 支持resume/seek时怎样用偏移和端点校验？
• IPv6压缩文本、128位边界与prefix需要哪些规范化步骤？