Is there a built in function in python which will convert a binary string, for example '111111111111', to the two's complement integer -1?
20 Answers
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
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,)
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
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.
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
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
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
Related