本文介绍一种分治式位运算方法，通过倍增策略在 o(n) 时间内构造满足“首尾为 1、相邻 1 间隔固定个 0”约束的二进制整数，显著优于朴素循环（o(n²)）和显式公式（涉及大数除法，实际更慢）。
本文介绍一种分治式位运算方法，通过倍增策略在 o(n) 时间内构造满足“首尾为 1、相邻 1 间隔固定个 0”约束的二进制整数，显著优于朴素循环（o(n²)）和显式公式（涉及大数除法，实际更慢）。
要生成形如 0b1001001001（即 1 后跟 distance−1 个 0，重复多次，且总长度严格小于 length）的整数，关键在于高效构造含 k 个 1 的模式，其中 k = 1 + (length − 2) // distance —— 这是满足约束的最大 1 的个数（首尾各占 1 位，中间每 distance 位容纳一个新 1）。
朴素实现（逐位左移或位或）时间复杂度为 O(k × distance) ≈ O(length)，但因每次 result |= pointer 涉及任意精度整数的位操作，在 Python 中底层仍需遍历 bit 位，实际为 O(k² × distance) = O(n²)。而基于幂级数公式的显式解：
(1 << (length + distance - 2 - ((length - 2) % distance))) // ((1 << distance) - 1)
虽数学简洁，却依赖大整数除法（Python 的 // 对超长整数非 O(1)），同样退化为 O(n²)。
✅ 正确解法是分治倍增：不逐个添加 1，而是每次将已构造的 1-bit 模式整体左移并合并，使 1 的数量近似翻倍。例如，已有 0b1001（2 个 1），想得到 3 个 1，可取前 2 个 1 的模式，左移 1×distance 位后与原值按位或；若需 5 个 1，可先构造 3 个，再叠加剩余 2 个……核心是每次合并尽可能多的未覆盖 1。
以下是优化后的迭代版本（推荐，清晰且无递归开销）：
def repeatdigit(length: int, distance: int) -> int:
# 计算所需 '1' 的总个数（至少首尾两个 1）
ones = 1 + (length - 2) // distance
if ones == 0:
return 0
if ones == 1:
return 1
result = 1 # 初始：仅一个 '1'
have = 1 # 当前已构造的 '1' 个数
while have < ones:
# 下一步最多可新增 min(have, ones - have) 个 '1'
add = min(have, ones - have)
# 将当前 result 左移 (add * distance) 位，使其末尾 '1' 与新位置对齐
result |= result << (add * distance)
have += add
return result执行过程示例（length=15, distance=4）：
→ ones = 1 + (15−2)//4 = 1 + 3 = 4
→ 初始 result=0b1, have=1
→ 第一轮：add = min(1, 3) = 1 → result = 0b1 | (0b1 , <code>have=2
→ 第二轮：add = min(2, 2) = 2 → result = 0b10001 | (0b10001 , <code>have=4 → 结束
输出 0b1000100010001，符合预期。
⚠️ 注意事项：
- 该算法时间复杂度为 O(log k) 次位或操作，每次位移/或操作在 Python 中对
m位整数耗时 O(m)，而最终结果最多约length位，故总时间复杂度为 O(length)，即 O(n)，满足要求； - 空间复杂度仅为 O(1) 额外变量（不计结果整数本身存储），远优于维护
length元素列表； -
distance必须 ≥ 1，且输入需保证ones ≥ 1（题设已约束有效性）； - 若
distance极大（接近length），add常为 1，退化为线性，但仍为 O(n)，而非 O(n²)。
此方法将位模式构造从“串行累加”升级为“分治拼接”，是位运算优化的经典范式，适用于高频 bit-mask 生成场景（如 SIMD 掩码、布隆过滤器初始化等）。
