Is there a built in function in python which will convert a binary string, for example '111111111111', to the two's complement integer -1?
This question is related to
python
bit-manipulation
twos-complement
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
>>> 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.
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
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.
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
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
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.
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,)
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
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)
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
Example 2: If the parameters are value=0x1F (31d, b11111) and bitWidth=6
Example 3: value = 0x80, bitWidth = 7
ValueError: Value: 128 out of range of 7-bit value.
Example 4: value = 0x80, bitWitdh = 8
Now, using what others have already posted, pass your bitstring into int(bitstring,2) and pass to the twos_complement method's value parameter.
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'
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
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
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
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
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)
Source: Stackoverflow.com