如何以O(n)时间复杂度生成符合指定重复二进制模式的整数

嘿，我完全get你的需求——要快速生成一个符合特定重复二进制规则的整数，用来当位操作的工具，而且因为length会超大，所以必须保证时间效率拉满，得是高效的线性级别的（甚至更优）。

首先先明确我们要的二进制数结构：它是1后面跟distance-1个0的模式重复多次，最后以1收尾，且总长度严格小于length。比如repeatdigit(10,3)得到0b1001001，就是1+00的模式重复三次，总长度7位，刚好小于10。

先聊聊为什么你觉得原来的两种方法慢：

• 循环方法：你可能误以为它是O(n²)，但其实不是！它的循环次数等于二进制数里1的个数，也就是floor((length-1)/distance)次，每次只做一次位或和固定距离的移位，Python里大整数的这些操作都是优化过的，实际时间复杂度是O(k)（k为1的个数）。不过如果是处理极端大的length，我们可以让它更直观一点，但本质效率已经很高了。
• 公式方法：这个确实可能慢到O(n²)，因为里面的大整数除法——当length很大时，1 << (length+distance-2 - ...)会生成一个位数超万的巨数，而大整数除法的时间复杂度和位数的平方成正比，这才是拖慢速度的元凶。

那怎么实现真正高效的方法呢？给你两种靠谱的实现：

优化后的位操作循环法（最贴合位操作需求） #

这个版本和你原来的循环思路一致，但调整了初始值，更直观，而且完全避免冗余操作：

def repeatdigit(length: int, distance: int) -> int:
    result = 1  # 先把最低位的1放上
    current_bit = 1 << distance  # 下一个要放1的位置
    max_bit = 1 << (length - 1)  # 最大允许的位（总长度要严格小于length，所以最高位不能到2^(length-1)）
    
    while current_bit < max_bit:
        result |= current_bit
        current_bit <<= distance  # 跳到下一个要放1的位置
    
    return result

验证例子：

• repeatdigit(10,3)：最终得到73，也就是0b1001001，完全符合预期。
• repeatdigit(15,4)：得到4369，对应0b1000100010001，正确。

时间复杂度：循环次数等于二进制数中1的个数，也就是floor((length-1)/distance)次。因为题目里说distance² < length，所以这个次数是O(√length)，比你要求的O(length)还要更高效。

等比数列迭代法（数学逻辑更直观） #

我们要生成的数本质是个等比数列的和：S = 1 + 2^distance + 2^(2*distance) + ... + 2^((k-1)*distance)，其中k是最大的整数满足总长度小于length。直接用等比数列公式会遇到大整数除法的问题，但我们可以迭代计算这个和，完全避开除法：

def repeatdigit(length: int, distance: int) -> int:
    ratio = 1 << distance  # 等比数列的公比：2^distance
    sum_geo = 1  # 初始项是1（2^0）
    current_term = ratio  # 下一项是2^distance
    max_term = 1 << (length - 1)  # 最大允许的项
    
    while current_term < max_term:
        sum_geo = sum_geo * ratio + 1  # 迭代累加：sum = sum*ratio + 1
        current_term *= ratio
    
    return sum_geo

这个方法的逻辑和位操作法完全等价，只是用数学上的等比数列迭代来实现，同样是O(k)的时间复杂度，适合喜欢数学逻辑的同学。

为什么原来的公式法慢？ #

再啰嗦一句，那个公式(1 << (length+distance-2 - ((length-2) % distance)))//((1 << distance) - 1)里的除法是罪魁祸首：当length很大时，被除数是一个位数高达length级别的巨数，而大整数除法的时间复杂度是O(m²)（m是数的位数），这才会导致O(n²)的慢速度，所以一定要避开这种大整数除法的实现。

最后，不管你选哪种方法，都能满足你对高效位操作工具的需求，完全不用再担心大length带来的性能问题～

备注：内容来源于stack exchange，提问作者Mr. W