Two's Complement in Python

Is there a built in function in python which will convert a binary string, for example '111111111111', to the two's complement integer -1?

Solution 1:

Two's complement subtracts off (1<<bits) if the highest bit is 1. Taking 8 bits for example, this gives a range of 127 to -128.

A function for two's complement of an int...

def twos_comp(val, bits):
    """compute the 2's complement of int value val"""
    if (val & (1 << (bits - 1))) != 0: # if sign bit is set e.g., 8bit: 128-255
        val = val - (1 << bits)        # compute negative value
    return val                         # return positive value as is

Going from a binary string is particularly easy...

binary_string = '1111' # or whatever... no '0b' prefix
out = twos_comp(int(binary_string,2), len(binary_string))

A bit more useful to me is going from hex values (32 bits in this example)...

hex_string = '0xFFFFFFFF' # or whatever... '0x' prefix doesn't matter
out = twos_comp(int(hex_string,16), 32)

Solution 2:

Since Python 3.2, there are built-in functions for byte manipulation: https://docs.python.org/3.4/library/stdtypes.html#int.to_bytes.

By combining to_bytes and from_bytes, you get

def twos(val_str, bytes):
    import sys
    val = int(val_str, 2)
    b = val.to_bytes(bytes, byteorder=sys.byteorder, signed=False)                                                          
    return int.from_bytes(b, byteorder=sys.byteorder, signed=True)

Check:

twos('11111111', 1)  # gives -1
twos('01111111', 1)  # gives 127

For older versions of Python, travc's answer is good but it does not work for negative values if one would like to work with integers instead of strings. A twos' complement function for which f(f(val)) == val is true for each val is:

def twos_complement(val, nbits):
    """Compute the 2's complement of int value val"""
    if val < 0:
        val = (1 << nbits) + val
    else:
        if (val & (1 << (nbits - 1))) != 0:
            # If sign bit is set.
            # compute negative value.
            val = val - (1 << nbits)
    return val

Solution 3:

It's not built in, but if you want unusual length numbers then you could use the bitstring module.

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

The same object can equivalently be created in several ways, including

>>> b = Bits(int=-1, length=12)

It just behaves like a string of bits of arbitrary length, and uses properties to get different interpretations:

>>> print a.int, a.uint, a.bin, a.hex, a.oct
-1 4095 111111111111 fff 7777

Solution 4:

>>> bits_in_word=12
>>> int('111111111111',2)-(1<<bits_in_word)
-1

This works because:

The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two (specifically, from 2^N for an N-bit two's complement). The two's complement of the number then behaves like the negative of the original number in most arithmetic, and it can coexist with positive numbers in a natural way.

Solution 5:

This will give you the two's complement efficiently using bitwise logic:

def twos_complement(value, bitWidth):
    if value >= 2**bitWidth:
        # This catches when someone tries to give a value that is out of range
        raise ValueError("Value: {} out of range of {}-bit value.".format(value, bitWidth))
    else:
        return value - int((value << 1) & 2**bitWidth)

How it works:

First, we make sure that the user has passed us a value that is within the range of the supplied bit range (e.g. someone gives us 0xFFFF and specifies 8 bits) Another solution to that problem would be to bitwise AND (&) the value with (2**bitWidth)-1

To get the result, the value is shifted by 1 bit to the left. This moves the MSB of the value (the sign bit) into position to be anded with 2**bitWidth. When the sign bit is '0' the subtrahend becomes 0 and the result is value - 0. When the sign bit is '1' the subtrahend becomes 2**bitWidth and the result is value - 2**bitWidth

Example 1: If the parameters are value=0xFF (255d, b11111111) and bitWidth=8

1. 0xFF - int((0xFF << 1) & 2**8)
2. 0xFF - int((0x1FE) & 0x100)
3. 0xFF - int(0x100)
4. 255 - 256
5. -1

Example 2: If the parameters are value=0x1F (31d, b11111) and bitWidth=6

1. 0x1F - int((0x1F << 1) & 2**6)
2. 0x1F - int((0x3E) & 0x40)
3. 0x1F - int(0x00)
4. 31 - 0
5. 31

Example 3: value = 0x80, bitWidth = 7

ValueError: Value: 128 out of range of 7-bit value.

Example 4: value = 0x80, bitWitdh = 8

1. 0x80 - int((0x80 << 1) & 2**8)
2. 0x80 - int((0x100) & 0x100)
3. 0x80 - int(0x100)
4. 128 - 256
5. -128

Now, using what others have already posted, pass your bitstring into int(bitstring,2) and pass to the twos_complement method's value parameter.