"Changing Bits" challenge

Question

Problem Statement:
Let A and B be two N bit numbers (MSB to the left). You are given initial values for A and B, and you have to write a program which processes three kinds of queries:

• set_a idx x: Set A[idx] to x, where \$0 \le idx < N\$, where A[idx] is idx'th least significant bit of A.

• set_b idx x: Set B[idx] to x, where \$0 \le idx < N\$, where B[idx] is idx'th least significant bit of B.

• get_c idx: Print C[idx], where \$C=A+B\$, and \$0\le idx\$

Input Format:
First line of input contains two integers \$N\$ and \$Q\$ consecutively (\$1 \le N \le 100000\$, \$1\le Q \le 500000\$). Second line is an \$N\$-bit binary number which denotes initial value of \$A\$, and the third line is an \$N\$-bit binary number denoting initial value of \$B\$. \$Q\$ lines follow, each containing a query as described above.

Output Format:
For each query of the type get_c, output a single digit \$0\$ or \$1\$. Output must be placed in a single line.

Sample Input:

5 5  
00000  
11111  
set_a 0 1  
get_c 5  
get_c 1  
set_b 2 0  
get_c 5

Sample Output:

100

I solved this question and I tried to optimize by reducing the number of calculations for bit addition, but am still getting time-limit-exceeded where the time exceeds 10 seconds for Python.

n, q = map(int, raw_input().split())
A_inp = list(raw_input())
B_inp = list(raw_input())
Query_output = []

def LSB(idx, n):
    return (n - 1) - (int(idx))

def Bit_Add(a, b, n):
    length = len(a)
    output = []
    carry = 0
    for i in range(length):
        if a[i] == "1" and b[i] == "1":
            if carry == 1:
                output.append(1)
                carry = 0
            else:
                output.append(0)
                carry = 1

        elif a[i] == "1" or b[i] == "1":
            if carry == 1:
                output.append(1)
                carry = 0
            else:
                output.append(0)
        else:
            if carry == 1:
                output.append(1)
                carry = 0

    if carry == 1:
        output.append(1)
    return output[::-1]
f = 0
for i in range(q):
    query = raw_input().split()
    if query[0][0:3] == "set":
        Value = query[0][4]
        idx = LSB(int(query[1]), n)
        if Value == "a":
            A_inp[idx] = query[2]
        elif Value == "b":
            B_inp[idx] = query[2]
        f = 0
    else:
        if f == 1:
            idx = LSB(query[1], len(output))
            Query_output.append(output[idx])
        else:
            output = Bit_Add(A_inp, B_inp, n)
            idx = LSB(query[1], len(output))
            Query_output.append(output[idx])
            f = 1


print int(''.join(["%d"%x for x in Query_output]))

Answer 1

The trick to this challenge is to actually change the number into bit operations, and not to do string manipulation as you do. So here are some hints on how to do this to get you started:

• Convert a binary string, text, of 0's and 1's into an int, use int(text, 2)
• To clear a bit at a given offset, use n & ~(1 << offset)
• To set a bit at a given offset, use n | (1 << offset)
• To get a bit at a given offset (shifted down again to one bit), use (n & (1 << offset)) >> offset)

Combine these, and you'll get a fast enough solution.

Style review of current code

Some tips according to PEP8:

• Use lower_snake_case for variable and function names - This looks a little better, and wouldn't throw off the syntax highlighter here on Code Review either... :-)
• Add a little vertical space in your code – Add two blank lines between functions, and add a blank line in natural segments within functions, like before if, else, for and while.
• Put all top level code in a main() function – Try to only keep imports, constants and functions at the top level, and start your code using a if __name__ == '__main__':' followed bymain()`
• Start using the print function, and str.format'ing– The % syntax will disappear some time, so start using the newer string formatting options already available.
• For Python 2 and large \$n\$'s use xrange() in for loops – Using range() will create the entire list, whilst xrange() will create a generator, and only give you one element at a time. For large numbers this has a noticeable effect on memory and time performance
• No need to create a list for join() – Instead of ''.join([ ... ]), you can simply use ''.join( ... ). The latter uses a generator instead of a list, similar to the range() vs xrange()

Refactored code running within time limit

So as not to spoil the fun for those wanting to solve this challenge by themselves, I've chosen to have the code hidden beneath a spoiler. That is if you hover over the block below you'll see the code.

def getBit(n, offset):
    return (n & (1 << offset)) >> offset

def clearBit(n, offset):
    return n & ~(1 << offset)

def setBit(n, offset):
    return n | (1 << offset)

def changing_bits_challenge():

    n, q = map(int, raw_input().split())
    a = int(raw_input(), 2)
    b = int(raw_input(), 2)

    c = []
    for _ in xrange(q):
        words = raw_input().split()
        operator = words[0][4]
        bit_number = int(words[1])

        if operator == 'c':
            c.append(getBit(a+b, bit_number))

        if operator == 'a':
            a = clearBit(a, bit_number) if words[2] == '0' 
                else setBit(a, bit_number)

        if operator == 'b':
            b = clearBit(b, bit_number) if words[2] == '0'
                else setBit(b, bit_number)

    print ''.join(str(i) for i in c)

changing_bits_challenge()