本文介绍一种时间复杂度为 O(n) 的位运算方法，用于生成满足“首尾为1、相邻1之间恰好有 distance−1 个0、总位长严格小于 length”条件的二进制整数，避免 O(n²) 的朴素循环或除法运算。
本文介绍一种时间复杂度为 o(n) 的位运算方法，用于生成满足“首尾为1、相邻1之间恰好有 `distance−1` 个0、总位长严格小于 `length`”条件的二进制整数，避免 o(n²) 的朴素循环或除法运算。
在高性能位操作场景中（例如 SIMD 掩码构造、布隆过滤器优化或密码学预处理），我们常需快速生成形如 0b1001001001（即 1 以固定步长 distance 重复出现）的大整数。该数在二进制中表现为周期性脉冲：每个 1 占据一位，其后紧跟 distance − 1 个 0，直至总位宽逼近但不超过 length。
朴素实现（逐位设置）时间复杂度为 O(n)，但此处的 n 是 1 的个数，而非总位长；而问题中实际瓶颈在于：当 length 极大（如 10⁶）时，若用循环 result |= 1 执行约 <code>O(length/distance) 次位移与或运算，单次 在 Python 中对大整数并非 O(1) —— 其底层涉及多精度整数的内存复制，<strong>整体实际复杂度接近 O(n²)</strong>（n 为位长）。
真正的 O(n) 解法核心思想是：倍增式合并（divide-and-conquer on bit groups），而非线性累加。我们先计算所需 1 的总数：
ones = 1 + (length - 2) // distance # 至少首位和末位各一个1，中间每distance位可塞一个1
然后递归/迭代地将已构造的含 have 个 1 的模式，左移 add * distance 位后与自身按位或，从而一次性追加 add 个新 1：
def repeatdigit(length: int, distance: int) -> int:
if length <= 1:
return 0 if length == 0 else 1
ones = 1 + (length - 2) // distance
if ones == 0:
return 0
if ones == 1:
return 1
result = 1 # 初始：仅一个1（最低位）
have = 1
while have < ones:
add = min(have, ones - have) # 贪心：尽可能翻倍，但不超过目标
result |= result << (add * distance)
have += add
return result✅ 复杂度分析：
- 循环至多执行
O(log(ones))次（每次have至少翻倍）； - 每次位移
和 <code>|运算处理的整数位宽约为O(have × distance)，而所有操作的总位运算量之和为 O(ones × distance) = O(length)； - 因此整体时间复杂度为 O(n)，其中
n = length（输入规模），空间复杂度为 O(1)（不计结果整数存储）。
? 关键技巧说明：
result 将当前所有 <code>1整体右移add个完整周期（每个周期长distance位），确保新旧1之间自然填充distance−1个0；-
result |= ...实现无重叠拼接（因移位后低位全零，不会干扰原有1）； -
add = min(have, ones - have)保证每次合并后have严格增加，且最终精确达到ones，无多余或缺失。
⚠️ 注意事项：
- 该算法依赖 Python 大整数的高效位移（CPython 中基于 Karatsuba 等优化，对中等长度表现优异）；
- 若
distance极小（如 1），则退化为全1数（2^ones - 1），仍保持 O(log ones) 步骤； - 实际使用前建议校验输入有效性（如
distance ≥ 1,length > 0），并注意length=1时仅返回1（0b1）。
此方法将空间敏感型任务（避免存储百万级 0/1 列表）与时间敏感型需求（O(n) 构造）完美结合，是位级算法工程中的典型优化范式。
