Complemento de dos en Python

¿Existe una función incorporada en python que convertirá una cadena binaria, por ejemplo ‘111111111111’, al entero- 1 del complemento de dos ?

El complemento de dos resta (1< si el bit más alto es 1. Tomando 8 bits, por ejemplo, esto da un rango de 127 a -128.

Una función para el complemento a dos de un 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 eg, 8bit: 128-255 val = val - (1 << bits) # compute negative value return val # return positive value as is 

Pasar de una cadena binaria es particularmente fácil ...

 binary_string = '1111' # or whatever... no '0b' prefix out = twos_comp(int(binary_string,2), len(binary_string)) 

Un poco más útil para mí es ir de valores hexadecimales (32 bits en este ejemplo) ...

 hex_string = '0xFFFFFFFF' # or whatever... '0x' prefix doesn't matter out = twos_comp(int(hex_string,16), 32) 

No está integrado, pero si desea números de longitud inusuales, entonces podría usar el módulo de cadena de bits .

 >>> from bitstring import Bits >>> a = Bits(bin='111111111111') >>> a.int -1 

El mismo objeto se puede crear de manera equivalente de varias maneras, incluyendo

 >>> b = Bits(int=-1, length=12) 

Simplemente se comporta como una cadena de bits de longitud arbitraria y utiliza propiedades para obtener diferentes interpretaciones:

 >>> print a.int, a.uint, a.bin, a.hex, a.oct -1 4095 111111111111 fff 7777 
 >>> bits_in_word=12 >>> int('111111111111',2)-(1< 

Esto funciona porque:

El complemento de dos de un número binario se define como el valor obtenido al restar el número de una gran potencia de dos (específicamente, de 2 ^ N para el complemento de dos bits de N). El complemento de dos del número se comporta como el negativo del número original en la mayoría de las operaciones aritméticas, y puede coexistir con números positivos de manera natural.

Desde Python 3.2, hay funciones incorporadas para la manipulación de bytes: https://docs.python.org/3.4/library/stdtypes.html#int.to_bytes .

Al combinar to_bytes y from_bytes, obtienes

 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) 

Comprobar:

 twos('11111111', 1) # gives -1 twos('01111111', 1) # gives 127 

Para versiones anteriores de Python, la respuesta de travc es buena, pero no funciona con valores negativos si a uno le gustaría trabajar con números enteros en lugar de cadenas. Una función de complemento de dos para la que f (f (val)) == val es verdadera para cada val es:

 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 

Un par de implementaciones (solo una ilustración, no para uso):

 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 

Esto le dará el complemento de los dos de manera eficiente utilizando la lógica bitwise:

 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) 

Cómo funciona:

Primero, nos aseguramos de que el usuario nos haya pasado un valor que esté dentro del rango del rango de bits suministrado (por ejemplo, alguien nos da 0xFFFF y especifica 8 bits). Otra solución a ese problema sería a modo de bit Y (&) el valor con (2 ** bitwidth) -1

Para obtener el resultado, el valor se desplaza 1 bit hacia la izquierda. Esto mueve el MSB del valor (el bit de signo) a la posición que se va a utilizar con 2**bitWidth . Cuando el bit de signo es '0', el sustituto se convierte en 0 y el resultado es value - 0 . Cuando el bit de signo es '1', el sustraendo se convierte en 2**bitWidth y el resultado es value - 2**bitWidth

Ejemplo 1: Si los parámetros son valor = 0xFF (255d, b11111111) y bitWidth = 8

  1. 0xFF - int ((0xFF << 1) y 2 ** 8)
  2. 0xFF - int ((0x1FE) & 0x100)
  3. 0xFF - int (0x100)
  4. 255 - 256
  5. -1

Ejemplo 2: Si los parámetros son valor = 0x1F (31d, b11111) y bitWidth = 6

  1. 0x1F - int ((0x1F << 1) y 2 ** 6)
  2. 0x1F - int ((0x3E) & 0x40)
  3. 0x1F - int (0x00)
  4. 31 - 0
  5. 31

Ejemplo 3: valor = 0x80, bitWidth = 7

ValueError: Value: 128 out of range of 7-bit value.

Ejemplo 4: valor = 0x80, bitWitdh = 8

  1. 0x80 - int ((0x80 << 1) y 2 ** 8)
  2. 0x80 - int ((0x100) & 0x100)
  3. 0x80 - int (0x100)
  4. 128 - 256
  5. -128

Ahora, utilizando lo que otros ya han publicado, pase su cadena de bits a int (cadena de bits, 2) y pase al parámetro de valor del método twos_complement.

No, no hay una función incorporada que convierta las cadenas binarias complementarias de dos en decimales.

Una simple función definida por el usuario que hace esto:

 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) 

Tenga en cuenta que esta función no toma el ancho de bits como parámetro, sino que los valores de entrada positivos deben especificarse con uno o más bits de cero iniciales.

Ejemplos:

 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 

Desde que erikb85 sacó a relucir el rendimiento, aquí está la respuesta de travc contra 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 

Entonces, la bitstring es, como se encuentra en la otra pregunta , casi un orden de magnitud más lento que int . Pero, por otro lado, es difícil superar la simplicidad: estoy convirtiendo un uint en una cadena de bits y luego un int ; tendrías que trabajar duro para no entender esto, o para encontrar un lugar donde introducir un error. Y como la respuesta de Scott Griffiths implica, hay mucha más flexibilidad para la clase que podría ser útil para la misma aplicación. Pero en la tercera parte, la respuesta de travc deja en claro lo que realmente está sucediendo, incluso un principiante debería ser capaz de comprender qué conversión de un int sin signo a un complemento con signo de 2 s significa que significa solo leer dos líneas de código.

De todos modos, a diferencia de la otra pregunta, que trataba de manipular directamente los bits, esta es una cuestión de aritmética en ints de longitud fija, solo de tamaño extraño. Así que supongo que si necesitas rendimiento, probablemente es porque tienes muchas de estas cosas, así que probablemente quieras que se vectorice. Adaptando la respuesta de travc a 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< 

Ahora:

 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 

Probablemente podría superar eso con un código C personalizado, pero probablemente no tenga que hacerlo.

En caso de que alguien necesite la dirección inversa también:

 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) 

debe emitir esto: 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000

Estoy usando Python 3.4.0

En Python 3 tenemos algunos problemas con la transformación de los tipos de datos.

Entonces … aquí les diré una sugerencia para aquellos (como yo) que trabajan mucho con cadenas hexagonales.

Tomaré un dato hexadecimal y lo complementaré:

 a = b'acad0109' compl = int(a,16)-pow(2,32) result=hex(compl) print(result) print(int(result,16)) print(bin(int(result,16))) 

resultado = -1397948151 o -0x5352fef7 o ‘-0b1010011010100101111111011110111’

Desafortunadamente, no hay una función incorporada para convertir un entero sin signo en un valor de signo complementario de dos, pero podemos definir una función para hacerlo usando operaciones bitwise:

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

La primera operación a nivel de bits se utiliza para firmar con extensión los números negativos (se establece el bit más significativo), mientras que la segunda se utiliza para capturar los 11 bits restantes. Esto funciona ya que los enteros en Python se tratan como valores de complemento de dos de precisión arbitraria.

Luego puede combinar esto con la función int para convertir una cadena de dígitos binarios a la forma de entero sin signo, y luego interpretarla como un valor firmado de 12 bits.

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

Una buena propiedad de esta función es que es idempotente, por lo que el valor de un valor ya firmado no cambiará.

 >>> s12(-1) -1 

Esto funciona para 3 bytes. El código en vivo está aquí

 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 

Ok, tuve este problema con el algoritmo de compresión uLaw con el tipo de archivo PCM wav . Y lo que descubrí es que el complemento de dos está haciendo un poco un valor negativo de algún número binario, como se puede ver aquí . Y después de consultar con wikipedia lo consideré cierto.

El chico lo explicó como encontrar el least significant bit y voltearlo todo después. Debo decir que todas estas soluciones anteriores no me ayudaron mucho. Cuando lo probé en 0x67ff me dio un poco de resultado en lugar de -26623 . Ahora las soluciones pueden haber funcionado si alguien supiera que el least significant bit es escanear la lista de datos, pero no lo sabía porque los datos en PCM varían. Así que aquí está mi respuesta:

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

Ahora, como el código es ilegible, te guiaré a través de la idea.

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

Este es cualquier valor hexadecimal, necesitaba una prueba para estar seguro, pero en general podría estar en cualquier rango de int . Por lo tanto, para no hacer un bucle en todo el conjunto de 65535 valores, short integer puede tener que decidí dividirlo por nibbles (4 bits). Se podría hacer así si no ha utilizado bitwise operators anteriormente.

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

Por lo tanto, estamos buscando el least significant bit por lo que aquí min(valid_nibble ) el min(valid_nibble ) . Aquí hemos conseguido el lugar donde está el primer nibble activo (con bit establecido). Ahora lo único que necesitamos es encontrar en qué lugar de nibble deseado está nuestro primer bit configurado.

 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< 

Ahora, aquí necesito aclarar algunas cosas, ya que ver ~ y ^ puede confundir a las personas que no están acostumbradas a esto:

XOR : ^ : 2 números son necesarios

Esta operación es un poco ilógica, por cada 2 bits que escanea, si ambos son 1 o 0, será 0, para todo lo demás 1.

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

Y otro ejemplo:

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

1's complement : ~ - no necesita ningún otro número

Esta operación voltea cada bit en un número. Es muy similar a lo que buscamos, pero no deja el bit menos significativo .

 0b10110 ~ 0b01001 

Y como podemos ver aquí, el complemento de 1 es el mismo que el número XOR de conjunto completo de bits.


Ahora que nos hemos entendido, obtendremos two's complement restaurando todos los bocados al bit menos significativo en el complemento de uno .

 data = ~data # one's complement of data 

Desafortunadamente, esto cambió todos los bits de nuestro número, por lo que solo necesitamos encontrar una manera de hacer retroceder los números que queremos. Podemos hacer eso con bit_shift ya que es la posición de bit de nuestro bit que necesitamos mantener. Entonces, al calcular la cantidad de datos que puede contener cierta cantidad de bits, podemos hacerlo con 2**n y para nibble obtenemos 16 ya que estamos calculando 0 en valores de bits.

 2**4 = 16 # in binary 1 0000 

Pero necesitamos los bytes después del 1 para que podamos usar eso para disminuir el valor en 1 y podamos obtenerlo.

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

Así que veamos la lógica en un ejemplo concreto:

  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 

Espero que esto te haya ayudado a ti o a cualquier novato que haya tenido el mismo problema y haya investigado su problema para encontrar la solución. Tenga en cuenta que este código que escribí es el código de Frankenstein, por lo que tuve que explicarlo. Se podría hacer más bonito, si alguien quiere que mi código sea bonito, por favor sea mi invitado.

Es mucho más fácil que todo eso …

para X en N bits: Comp = (-X) y (2 ** N – 1)

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