Python - Most effective way to implement two's complement?

Question

Two's complement is when you inverse bits then add a binary 1 digit. So for example...

0011001
apply two's complement
1. inverse the bits, 1100110
2. add a binary digit, 1100110 + 1 = 1100111

Another example to show overflow situation...

1001100
apply two's complement
1. inverse the bits, 0110011
2. add a binary digit, 0110011 + 1 = 0110100

What would be the best way to implement this in python. So far I have this code, but I would like it to be more efficient because I'm using this method too much.

def toTwosComplement(binarySequence):
    convertedSequence = [0] * len(binarySequence)
    carryBit = 1
    # INVERT THE BITS
    for i in range(0, len(binarySequence)):
        if binarySequence[i] == '0':
            convertedSequence[i] = 1
        else:
            convertedSequence[i] = 0

    # ADD BINARY DIGIT 1

    if convertedSequence[-1] == 0: #if last digit is 0, just add the 1 then there's no carry bit so return
            convertedSequence[-1] = 1
            return ''.join(str(x) for x in convertedSequence)

    for bit in range(0, len(binarySequence)):
        if carryBit == 0:
            break
        index = len(binarySequence) - bit - 1
        if convertedSequence[index] == 1:
            convertedSequence[index] = 0
            carryBit = 1
        else:
            convertedSequence[index] = 1
            carryBit = 0

    return ''.join(str(x) for x in convertedSequence)

if __name__ == '__main__':
    print toTwosComplement('00110010101101001')

My question is, can I optimise this algorithm because at the moment it is running too slow for the amount of binary code I have to run it through.

I searched that question but it gives the value of the two's complement representation. I want it just as the two's complement string. — Ogen, May 29 '13 at 12:14
`bin()` gives you the binary representation of a integer value, or use `format(value, 'b')` to get a binary string without the `0b` prefix. Use `format(value, '08b')` to format it to a `0`-padded string of length 8. — Martijn Pieters, May 29 '13 at 12:17
Nah, just upvote answers on the other page; all I gave you is a way to get back to a string with 0 and 1 digits. — Martijn Pieters, May 29 '13 at 12:31

spicavigo · Accepted Answer · 2013-05-29T12:08:37.303

6

x=int(a,2)
num_bits = 10
print x - (1 << num_bits)

I think this should solve the problem

edited May 29 '13 at 12:08

answered May 29 '13 at 12:01

spicavigo

4,116
22
28

a = '1001', ~(int(a,2)). I got -10. I don't understand can you elaborate? – Ogen May 29 '13 at 12:05
@Clay `~` is a [bitwise operator](http://docs.python.org/2/reference/expressions.html#unary-arithmetic-and-bitwise-operations) – TerryA May 29 '13 at 12:07
I'm still getting a wrong answer, I inputted '1001' into **a** and I got -1015 – Ogen May 29 '13 at 12:12
Change number of bits to the one that you want. – spicavigo May 29 '13 at 12:21
3

Should be `print bin(x - (1 << 1))` – matino May 29 '13 at 12:24

score 1 · Answer 2 · answered May 29 '13 at 13:34

1

Try this:

x = 0b11001100
complement = abs(~x) + 0b1
print bin(complement)

answered May 29 '13 at 13:34

ElmoVanKielmo

10,907
2
32
46

1

Negation must happen [after taking the absolute value](https://en.wikipedia.org/wiki/Two%27s_complement#Converting_to_two.27s_complement_representation), i.e., `~abs(x) + 0b1`. – 0 _ Nov 10 '14 at 12:01

score 0 · Answer 3 · answered May 29 '13 at 12:34

0

using bitstring package

>>> from bitstring import BitArray
>>> a = BitArray(bin='111111111111')
>>> a.int
-1

answered May 29 '13 at 12:34

kiriloff

25,609
37
148
229

My desired output for your input would be '000000000001'. – Ogen May 29 '13 at 12:36
try same with `intne` – kiriloff May 29 '13 at 12:55

Python - Most effective way to implement two's complement?

3 Answers3

Linked