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
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.
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)
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.
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:
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.
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
0xFF - int((0xFF << 1) & 2**8)
0xFF - int((0x1FE) & 0x100)
0xFF - int(0x100)
255 - 256
-1
Example 2: If the parameters are value=0x1F (31d, b11111) and bitWidth=6
0x1F - int((0x1F << 1) & 2**6)
0x1F - int((0x3E) & 0x40)
0x1F - int(0x00)
31 - 0
31
Example 3: value = 0x80, bitWidth = 7
ValueError: Value: 128 out of range of 7-bit value.
Example 4: value = 0x80, bitWitdh = 8
0x80 - int((0x80 << 1) & 2**8)
0x80 - int((0x100) & 0x100)
0x80 - int(0x100)
128 - 256
-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.
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
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
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)
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
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:
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}')
