如何在Python中优化str.replace（）

Question

我正在处理二进制字符串（即它仅包含1和0），并且我需要运行N次函数。此函数将字符串中的“ 01”的任何实例替换为“ 10”。但是，str.replace需要太多时间来处理输出，特别是当字符串的长度以及N的长度可以达到10 ^ 6时。

我已经尝试实现正则表达式，但是它没有为我提供任何优化，而是花了更多的时间来执行任务。

例如，如果提供给我的字符串是01011并且N等于1，则输出应为10101。类似地，如果N变为2，则输出将变为11010，依此类推。

是否在python中对str.replace进行了优化，或者我可以做一些操作来优化代码？

Answer 1

让我们将输入视为形成无符号整数的位，可能是一个非常大的整数。例如：

  1001 1011  # input number X
  0100 1101  # Y = X>>1 = X//2 -- to get the previous bit to the same column
  1001 0010  # Z1 = X & ~Y -- We are looking for 01, i.e. 1 after previous 0
  0001 0010  # Z2 = Z1 with the highest bit cleared, because we don't want
             # to process the implicit 0 before the number
  1010 1101  # output = X + Z2, this adds 1 where 01's are;
             # 1 + 01 = 10, this is what we want

因此，我们只需很少的算术运算就可以处理整个列表。

更新：示例代码，我尝试解决有关前导零的评论。

xstr = input("Enter binary number: ")
x = int(xstr, base=2)
digits = len(xstr)
mask = 2**(digits-1) - 1 
print("{:0{width}b}".format(x,width=digits))

while True:
    z2 = x & ~(x >> 1) & mask
    if z2 == 0:
        print("final state")
        break
    x += z2
    print("{:0{width}b}".format(x,width=digits))