Two's Complement in Python

Question

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

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

Answer 2

Since Python 3.2, there are built-in functions for byte manipulation: https://docs.python.org/3/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

Answer 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

Answer 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.

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

Answer 6

A couple of implementations (just an illustration, not intended for use):

def to_int(bin):
    x = int(bin, 2)
    if bin[0] == '1': # "sign bit", big-endian
       x -= 2**len(bin)
    return x

def to_int(bin): # from definition
    n = 0
    for i, b in enumerate(reversed(bin)):
        if b == '1':
           if i != (len(bin)-1):
              n += 2**i
           else: # MSB
              n -= 2**i 
    return n

Answer 7

in case someone needs the inverse direction too:

def num_to_bin(num, wordsize):
    if num < 0:
        num = 2**wordsize+num
    base = bin(num)[2:]
    padding_size = wordsize - len(base)
    return '0' * padding_size + base

for i in range(7, -9, -1):
    print num_to_bin(i, 4)

should output this: 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000

Answer 8

No, there is no builtin function that converts two's complement binary strings into decimals.

A simple user defined function that does this:

def two2dec(s):
  if s[0] == '1':
    return -1 * (int(''.join('1' if x == '0' else '0' for x in s), 2) + 1)
  else:
    return int(s, 2)

Note that this function doesn't take the bit width as parameter, instead positive input values have to be specified with one or more leading zero bits.

Examples:

In [2]: two2dec('1111')
Out[2]: -1

In [3]: two2dec('111111111111')
Out[3]: -1

In [4]: two2dec('0101')
Out[4]: 5

In [5]: two2dec('10000000')
Out[5]: -128

In [6]: two2dec('11111110')
Out[6]: -2

In [7]: two2dec('01111111')
Out[7]: 127

Answer 9

You can use the bit_length() function to convert numbers to their two's complement:

def twos_complement(j):
   return j-(1<<(j.bit_length()))

In [1]: twos_complement(0b111111111111)                                                                                                                                                             
Out[1]: -1

Answer 10

you could convert the integer to bytes and then use struct.unpack to convert:

from struct import unpack

x = unpack("b", 0b11111111.to_bytes(length=1, byteorder="little"))
print(x)  # (-1,)

Answer 11

Since erikb85 brought up performance, here's travc's answer against Scott Griffiths':

In [534]: a = [0b111111111111, 0b100000000000, 0b1, 0] * 1000
In [535]: %timeit [twos_comp(x, 12) for x in a]
100 loops, best of 3: 8.8 ms per loop
In [536]: %timeit [bitstring.Bits(uint=x, length=12).int for x in a]
10 loops, best of 3: 55.9 ms per loop

So, bitstring is, as found in the other question, almost an order of magnitude slower than int. But on the other hand, it's hard to beat the simplicity—I'm converting a uint to a bit-string then to an int; you'd have to work hard not to understand this, or to find anywhere to introduce a bug. And as Scott Griffiths' answer implies, there's a lot more flexibility to the class which might be useful to the same app. But on the third hand, travc's answer makes it clear what's actually happening—even a novice should be able to understand what conversion from an unsigned int to a 2s complement signed int means just from reading 2 lines of code.

Anyway, unlike the other question, which was about directly manipulating bits, this one is all about doing arithmetic on fixed-length ints, just oddly-sized ones. So I'm guessing if you need performance, it's probably because you have a whole bunch of these things, so you probably want it to be vectorized. Adapting travc's answer to numpy:

def twos_comp_np(vals, bits):
    """compute the 2's compliment of array of int values vals"""
    vals[vals & (1<<(bits-1)) != 0] -= (1<<bits)
    return vals

Now:

In [543]: a = np.array(a)
In [544]: %timeit twos_comp_np(a.copy(), 12)
10000 loops, best of 3: 63.5 µs per loop

You could probably beat that with custom C code, but you probably don't have to.

Answer 12

Unfortunately there is no built-in function to cast an unsigned integer to a two's complement signed value, but we can define a function to do so using bitwise operations:

def s12(value):
    return -(value & 0b100000000000) | (value & 0b011111111111)

The first bitwise-and operation is used to sign-extend negative numbers (most significant bit is set), while the second is used to grab the remaining 11 bits. This works since integers in Python are treated as arbitrary precision two's complement values.

You can then combine this with the int function to convert a string of binary digits into the unsigned integer form, then interpret it as a 12-bit signed value.

>>> s12(int('111111111111', 2))
-1
>>> s12(int('011111111111', 2))
2047
>>> s12(int('100000000000', 2))
-2048

One nice property of this function is that it's idempotent, thus the value of an already signed value will not change.

>>> s12(-1)
-1

Answer 13

Use ~, ^, and a mask (mask determines the total number of bits)

# Given negative value, obtain its two's complement form in 16 bits

>>> mask = (1 << 16) - 1
>>> a = -6
>>> bin(~(a ^ mask))
'0b1111111111111010'

# Given 16-bit signed binary string, return the integer value
>>> mask = (1 << 16) - 1
>>> b = '1111111111110101'
>>> ~(int(b, 2) ^ mask)
-11

Answer 14

I'm using Python 3.4.0

In Python 3 we have some problems with data types transformation.

So... here I'll tell a tip for those (like me) that works a lot with hex strings.

I'll take an hex data and make an complement it:

a = b'acad0109'

compl = int(a,16)-pow(2,32)

result=hex(compl)
print(result)
print(int(result,16))
print(bin(int(result,16)))

result = -1397948151 or -0x5352fef7 or '-0b1010011010100101111111011110111'

Answer 15

This works for 3 bytes. Live code is here

def twos_compliment(byte_arr):
   a = byte_arr[0]; b = byte_arr[1]; c = byte_arr[2]
   out = ((a<<16)&0xff0000) | ((b<<8)&0xff00) | (c&0xff)
   neg = (a & (1<<7) != 0)  # first bit of a is the "signed bit." if it's a 1, then the value is negative
   if neg: out -= (1 << 24)
   print(hex(a), hex(b), hex(c), neg, out)
   return out


twos_compliment([0x00, 0x00, 0x01])
>>> 1

twos_compliment([0xff,0xff,0xff])
>>> -1

twos_compliment([0b00010010, 0b11010110, 0b10000111])
>>> 1234567

twos_compliment([0b11101101, 0b00101001, 0b01111001])
>>> -1234567

twos_compliment([0b01110100, 0b11001011, 0b10110001])
>>> 7654321

twos_compliment([0b10001011, 0b00110100, 0b01001111])
>>> -7654321

Answer 16

Ok i had this issue with uLaw compression algorithm with PCM wav file type. And what i've found out is that two's complement is kinda making a negative value of some binary number as can be seen here.And after consulting with wikipedia i deemed it true.

The guy explained it as finding least significant bit and flipping all after it. I must say that all these solutions above didn't help me much. When i tried on 0x67ff it gave me some off result instead of -26623. Now solutions may have worked if someone knew the least significant bit is scanning list of data but i didn't knew since data in PCM varies. So here is my answer:

max_data = b'\xff\x67' #maximum value i've got from uLaw data chunk to test

def twos_compliment(short_byte): # 2 bytes 
    short_byte = signedShort(short_byte) # converting binary string to integer from struct.unpack i've just shortened it.
    valid_nibble = min([ x*4 for x in range(4) if (short_byte>>(x*4))&0xf ])
    bit_shift = valid_nibble + min( [ x for x in [1,2,4,8] if ( ( short_byte>>valid_nibble )&0xf )&x ] )
    return (~short_byte)^( 2**bit_shift-1 )

data  = 0x67ff
bit4 = '{0:04b}'.format
bit16 = lambda x: ' '.join( map( bit4, reversed([ x&0xf, (x>>4)&0xf, (x>>8)&0xf, (x>>12)&0xf ]) ) )

# print( bit16(0x67ff) , ' : ', bit16( twos_compliment(  b'\xff\x67' ) ) )
# print( bit16(0x67f0) , ' : ', bit16( twos_compliment(  b'\xf0\x67' ) ) )
# print( bit16(0x6700) , ' : ', bit16( twos_compliment(  b'\x00\x67' ) ) )
# print( bit16(0x6000) , ' : ', bit16( twos_compliment(  b'\x00\x60' ) ) )
print( data, twos_compliment(max_data) )

Now since code is unreadable i will walk you through the idea.

## example data, for testing... in general unknown
data = 0x67ff # 26623 or 0110 0111 1111 1111 

This is just any hexadecimal value, i needed test to be sure but in general it could be anything in range of int. So not to loop over whole bunch of 65535 values short integer can have i decided to split it by nibbles ( 4 bits ). It could be done like this if you haven't used bitwise operators before.

nibble_mask = 0xf # 1111
valid_nibble = []

for x in range(4): #0,1,2,3 aka places of bit value
    # for individual bits you could go 1<<x as you will see later

    # x*4 is because we are shifting bit places , so 0xFA>>4 = 0xF
    #     so 0x67ff>>0*4 = 0x67ff
    #     so 0x67ff>>1*4 = 0x67f
    #     so 0x67ff>>2*4 = 0x67
    #     so 0x67ff>>3*4 = 0x6
    # and nibble mask just makes it confided to 1 nibble so 0xFA&0xF=0xA
    if (data>>(x*4))&nibble_mask: valid_nibble.append(x*4) # to avoid multiplying it with 4 later 

So we are searching for least significant bit so here the min(valid_nibble ) will suffice. Here we've gotten the place where first active (with setted bit) nibble is. Now we just need is to find where in desired nibble is our first setted bit.

bit_shift = min(valid_nibble)
for x in range(4): 
    # in my example above [1,2,4,8] i did this to spare python calculating 
    ver_data = data>>min(bit_shift ) # shifting from 0xFABA to lets say 0xFA
    ver_data &= nibble_mask # from 0xFA to 0xA 
    if ver_data&(1<<x): 
        bit_shift += (1<<x)
        break

---

Now here i need to clarify somethings since seeing ~ and ^ can confuse people who aren't used to this:

XOR: ^: 2 numbers are necesery

This operation is kinda illogical, for each 2 bits it scans if both are either 1 or 0 it will be 0, for everything else 1.

 0b10110
^0b11100
--------- 
 0b01010   

And another example:

 0b10110
^0b11111
---------
 0b01001

1's complement : ~ - doesn't need any other number

This operation flips every bit in a number. It is very similar to what we are after but it doesn't leave the least significant bit.

0b10110  
~  
0b01001

And as we can see here 1's compliment is same as number XOR full set bits.

---

Now that we've understood each other, we will getting two's complement by restoring all bites to least significant bit in one's complement.

data = ~data # one's complement of data 

This unfortunately flipped all bits in our number, so we just need to find a way to flip back the numbers we want. We can do that with bit_shift since it is bit position of our bit we need to keep. So when calculating number of data some number of bits can hold we can do that with 2**n and for nibble we get 16 since we are calculating 0 in values of bits.

2**4 = 16 # in binary 1 0000 

But we need the bytes after the 1 so we can use that to diminish the value by 1 and we can get.

2**4 -1 = 15 # in binary 0 1111 

So lets see the logic in concrete example:

 0b110110
 lsb = 2 # binary 10 

~0b110110
----------
 0b001001 # here is that 01 we don't like  

 0b001001
^0b000011 # 2**2 = 4 ; 4-1 = 3 in binary 0b11 
--------- 
 0b001010

I hope this help'd you or any newbie that had this same problem and researched their a** off finding the solution. Have in mind this code i wrote is frankenstein code , that i why i had to explain it. It could be done more prettier, if anyone wants to make my code pretty please be my guest.

Answer 17

Here's a version to convert each value in a hex string to it's two's complement version.

In [5159]: twoscomplement('f0079debdd9abe0fdb8adca9dbc89a807b707f')                                                                                                 
Out[5159]: '10097325337652013586346735487680959091'


def twoscomplement(hm): 
   twoscomplement='' 
   for x in range(0,len(hm)): 
       value = int(hm[x],16) 
       if value % 2 == 1: 
         twoscomplement+=hex(value ^ 14)[2:] 
       else: 
         twoscomplement+=hex(((value-1)^15)&0xf)[2:] 
   return twoscomplement            

Answer 18

Still a very relevant question, but none of the answers worked in my scenario - which is surprising.

Here's a very simple function to calculate n-bit 2's complement integer values from an integer value.

This function especially ensures that the returned value is NOT seen as a negative value by python, as it breaks the very nature of 2's complement numbers.

2's complement numbers were originally created to work with both positive and negative values on architectures that do not natively support them. It's a conversion and is all about using the bits available to represent and calculate with both positive and negative numbers.

Therefore the number of bits can be specified, defaults to 16, and can by setting it to 0, be set to the required number of bits for the given value.

    def twos_comp(val, bits=16):
        """compute the 2's complement of int value """
        if bits == 0:      # Use as many bits needed for the value.
            bits = val.bit_length()
        return ((val & (2 ** bits) - 1) - (2 ** bits)) * -1

Test code:

    value = 6752
    print(f'{value:05d} = 0x{value:04x} = 0b{value:016b}')
    
    value = twos_comp(value)
    print(f'{value:05d} = 0x{value:04x} = 0b{value:016b}')
    
    value = twos_comp(value)
    print(f'{value:05d} = 0x{value:04x} = 0b{value:016b}')

Test code output:

 06752 = 0x1a60 = 0b0001101001100000
 01440 = 0x05a0 = 0b0000010110100000
 06752 = 0x1a60 = 0b0001101001100000

Answer 19

Subtract 2^nbits from negative values:

In [75]: (lambda x: int(x,2) - 2**len(x)*int(x[0]))('10000000')
Out[75]: -128

In [76]: (lambda x: int(x,2) - 2**len(x)*int(x[0]))('01111111')
Out[76]: 127

In [77]: (lambda x: int(x,2) - 2**len(x)*int(x[0]))('0111')
Out[77]: 7

In [78]: (lambda x: int(x,2) - 2**len(x)*int(x[0]))('1111001')
Out[78]: -7

• works for any length input
• handles positive and negative values correctly
• NOTE: positive values must have leading zeros

Answer 20

It's much easier than all that...

for X on N bits: Comp = (-X) & (2**N - 1)

def twoComplement(number, nBits):
    return (-number) & (2**nBits - 1)