Python - Applying Two's Complement to a String

Question

I am trying to add the Two's Complement to a Binary number represented with a string. Assuming the string has already been flipped, how would I go about "adding" 1 to the last character, and replacing the other characters in the string as needed?

Example: 100010 is flipped to 011101, and is represented as a string. How would you apply the Two's Complement to the 011101 string?

One part of this that really has me puzzled is if the user enters a binary number that, when the two's complement is applied, involves a lot of carrying.

Answer 1

I'd just do it as a number, then convert it back.

def tobin(x, count=8):
    # robbed from http://code.activestate.com/recipes/219300/
    return "".join(map(lambda y:str((x>>y)&1), range(count-1, -1, -1)))

def twoscomp(num_str):
    return tobin(-int(num_str,2),len(num_str))

print twoscomp('01001001') # prints 10110111
print twoscomp('1000')     # prints 1000 (because two's comp is cool like that)
print twoscomp('001')      # prints 111

Answer 2

Just for variety, here's yet another way based on the fact the Two's Complement is defined as the One's Complement plus one. This cheats a little and converts the intermediate one's complement string value into an integer to add one to it, and then converts it back to a binary string using the new built-in bin() function added in Python 2.6.

def onescomp(binstr):
    return ''.join('1' if b=='0' else '0' for b in binstr)

def twoscomp(binstr):
    return bin(int(onescomp(binstr),2)+1)[2:]

print twoscomp('01001001') # prints 10110111
print twoscomp('011101')   # prints 100011
print twoscomp('001')      # prints 111

Answer 3

if you want to do it without converting back to a number, start from the right of the string until you find the first 1, then flip all chars to its left.