How to optimize str.replace() in Python

Question

I am working on a binary string (i.e it only contains 1 and 0) and I need to run a function N number of times. This function replaces any instance of '01' in string to '10'. However, str.replace takes too much time to process the output, especially when the the length of string as well as N can be as big as 10^6.

I have tried implementing regex but it hasn't provided me with any optimization, instead taking more time to perform the task.

For example, if the string given to me is 01011 and N is equal to 1, then the output should be 10101. Similarly, if N becomes 2, the output becomes 11010 and so on.

Are there any optimizations of str.replace in python or is there any bit manipulation I could do to optimize my code?

Answer 1

Let's think of the input as bits forming an unsigned integer, possible a very large one. For example:

  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

Thus we can process the whole list just with few arithmetic operations.

---

Update: sample code, I tried to address the comment about leading zeroes.

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))