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

User · Answer

It s not built in  but if you want unusual length numbers then you could use the bitstring module    gt  gt  gt  from bitstring import Bits  gt  gt  gt  a   Bits bin  111111111111    gt  gt  gt  a int -1   The same object can equivalently be created in several ways  including   gt  gt  gt  b   Bits int -1  length 12    It just behaves like a string of bits of arbitrary length  and uses properties to get different interpretations    gt  gt  gt  print a int  a uint  a bin  a hex  a oct -1 4095 111111111111 fff 7777

User · Answer

Two s complement subtracts off  1 lt  lt 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  amp   1  lt  lt   bits - 1       0    if sign bit is set e g   8bit  128-255         val   val -  1  lt  lt  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

User · Answer

This will give you the two s complement efficiently using bitwise logic   def twos complement value  bitWidth       if value  gt   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  lt  lt  1   amp  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   amp   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  lt  lt  1   amp  2  8  0xFF - int  0x1FE   amp  0x100  0xFF - int 0x100  255  - 256 -1   Example 2  If the parameters are value 0x1F  31d  b11111  and bitWidth 6   0x1F - int  0x1F  lt  lt  1   amp  2  6  0x1F - int  0x3E   amp  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  lt  lt  1   amp  2  8  0x80 - int  0x100   amp  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

User · Answer

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

User · Answer

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 gt  gt  x 4   amp 0xf        bit shift   valid nibble   min    x for x in  1 2 4 8  if     short byte gt  gt valid nibble   amp 0xf   amp x         return   short byte    2  bit shift-1    data    0x67ff bit4     0 04b   format bit16   lambda x      join  map  bit4  reversed   x amp 0xf   x gt  gt 4  amp 0xf   x gt  gt 8  amp 0xf   x gt  gt 12  amp 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 lt  lt x as you will see later        x 4 is because we are shifting bit places   so 0xFA gt  gt 4   0xF           so 0x67ff gt  gt 0 4   0x67ff           so 0x67ff gt  gt 1 4   0x67f           so 0x67ff gt  gt 2 4   0x67           so 0x67ff gt  gt 3 4   0x6       and nibble mask just makes it confided to 1 nibble so 0xFA amp 0xF 0xA     if  data gt  gt  x 4   amp 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 gt  gt min bit shift     shifting from 0xFABA to lets say 0xFA     ver data  amp   nibble mask   from 0xFA to 0xA      if ver data amp  1 lt  lt x            bit shift     1 lt  lt 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

User · Answer

It s much easier than all that     for X on N bits  Comp    -X   amp   2  N - 1   def twoComplement number  nBits       return  -number   amp   2  nBits - 1

User · Answer

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  lt  0          val    1  lt  lt  nbits    val     else          if  val  amp   1  lt  lt   nbits - 1       0                If sign bit is set                compute negative value              val   val -  1  lt  lt  nbits      return val

User · Answer

you could convert the integer to bytes and then use struct unpack to convert  from struct import unpack  x   unpack  quot b quot   0b11111111 to bytes length 1  byteorder  quot little quot    print x      -1

User · Answer

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  amp   1 lt  lt  bits-1      0  -   1 lt  lt 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

User · Answer

You can use the bit length   function to convert numbers to their two s complement    def twos complement j      return j- 1 lt  lt  j bit length      In  1   twos complement 0b111111111111                                                                                                                                                               Out 1   -1

User · Answer

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

User · Answer

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  amp  0b100000000000     value  amp  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    gt  gt  gt  s12 int  111111111111   2   -1  gt  gt  gt  s12 int  011111111111   2   2047  gt  gt  gt  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    gt  gt  gt  s12 -1  -1

User · Answer

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  amp 0xf  2       return twoscomplement

User · Answer

in case someone needs the inverse direction too   def num to bin num  wordsize       if num  lt  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

User · Answer

gt  gt  gt  bits in word 12  gt  gt  gt  int  111111111111  2 - 1 lt  lt 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

User · Answer

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

User · Answer

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 lt  lt 16  amp 0xff0000      b lt  lt 8  amp 0xff00     c amp 0xff     neg    a  amp   1 lt  lt 7     0     first bit of a is the  signed bit   if it s a 1  then the value is negative    if neg  out -   1  lt  lt  24     print hex a   hex b   hex c   neg  out     return out   twos compliment  0x00  0x00  0x01    gt  gt  gt  1  twos compliment  0xff 0xff 0xff    gt  gt  gt  -1  twos compliment  0b00010010  0b11010110  0b10000111    gt  gt  gt  1234567  twos compliment  0b11101101  0b00101001  0b01111001    gt  gt  gt  -1234567  twos compliment  0b01110100  0b11001011  0b10110001    gt  gt  gt  7654321  twos compliment  0b10001011  0b00110100  0b01001111    gt  gt  gt  -7654321

[python] Two's Complement in Python

Examples related to python

Examples related to bit-manipulation

Examples related to twos-complement