font python bit-manipulation twos-complement

font - subplot title python



Complemento de dos en Python (14)

¿Hay una función incorporada en python que convertirá una cadena binaria, por ejemplo ''111111111111'', en el entero complementario de dos -1?

Dado que erikb85 trajo 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, 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 luego en un int ; tendrías que esforzarte para no entender esto, o para encontrar un lugar donde introducir un error. Y como implica la respuesta de Scott Griffiths, hay mucha más flexibilidad para la clase que podría ser útil para la misma aplicación. Pero, por otro lado, la respuesta de travc deja en claro lo que está sucediendo realmente: incluso un novato debe ser capaz de comprender qué conversión de un int sin signo a un complemento 2 firmado int significa simplemente leer 2 líneas de código.

De todos modos, a diferencia de la otra pregunta, que trata sobre la manipulación directa de bits, esta se trata de hacer aritmética en ints de longitud fija, solo de tamaño impar. Así que supongo que si necesitas rendimiento, es probablemente porque tienes un montón de estas cosas, por lo que probablemente quieras que se vectoricen. 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<<bits) return vals

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 puedas vencer eso con el código C personalizado, pero probablemente no sea necesario.

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 para valores negativos si se desea trabajar con enteros en lugar de cadenas. Una función de complemento de dos para la cual 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

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

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

def twoComplement(number, nBits): return (-number) & (2**nBits - 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

Esto le dará el complemento a dos de manera eficiente usando lógica bit a bit:

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 nivel 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 su posición para ser anded con 2**bitWidth . Cuando el bit de signo es ''0'', el sustraendo se vuelve 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 value = 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 value = 0x1F (31d, b11111) y bitWidth = 6

  1. 0x1F - int ((0x1F << 1) y 2 ** 6)
  2. 0x1F - int ((0x3E) y 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) y 0x100)
  3. 0x80 - int (0x100)
  4. 128 - 256
  5. -128

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

Estoy usando Python 3.4.0

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

Entonces ... aquí les contaré un consejo para aquellos (como yo) que trabajan mucho con cadenas hexagonales.

Tomaré un dato hexadecimal y lo completaré:

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

Lamentablemente, no hay función incorporada para convertir un entero sin signo en un valor con signo del complemento a dos, pero podemos definir una función para hacerlo utilizando operaciones en modo bit:

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

La primera operación bitwise-and se usa para firmar-ampliar números negativos (se establece el bit más significativo), mientras que el segundo se usa para capturar los 11 bits restantes. Esto funciona ya que los enteros en Python se tratan como valores de complemento de precisión arbitraria dos.

A continuación, puede combinar esto con la función int para convertir una cadena de dígitos binarios en el formato entero sin signo, y luego interpretarlo 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 tanto, el valor de un valor ya firmado no cambiará.

>>> s12(-1) -1

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 usa propiedades para obtener diferentes interpretaciones:

>>> print a.int, a.uint, a.bin, a.hex, a.oct -1 4095 111111111111 fff 7777

No, no hay una función integrada que convierta las cadenas binarias del complemento de dos en decimales.

Una función simple 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 del bit como parámetro, sino que los valores de entrada positivos deben especificarse con uno o más bits 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

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 a dos está haciendo un valor negativo de algunos números binarios, como se puede ver aquí . Y después de consultar con wikipedia consideré cierto.

El chico lo explicó como encontrar least significant bit y lanzar todo después. Debo decir que todas estas soluciones anteriores no me ayudaron mucho. Cuando probé 0x67ff me dio un resultado fuera de -26623 . Ahora las soluciones pueden haber funcionado si alguien sabía que el least significant bit es escanear la lista de datos, pero yo no 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 que el código no se puede leer, lo guiaré a través de la idea.

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

Esto es cualquier valor hexadecimal, necesitaba prueba para estar seguro, pero en general podría ser cualquier cosa en el rango de int . Por lo tanto, para no recorrer todo un conjunto de 65535 valores, short integer puede haber decidido dividirlo en nibbles (4 bits). Podría hacerse 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<<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

Así que estamos buscando least significant bit por lo que aquí el min(valid_nibble ) será suficiente. Aquí conseguimos el lugar donde se encuentra el primer nibble activo (con bit definido). Ahora solo necesitamos encontrar dónde en el mordisco deseado es nuestro primer bit establecido.

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

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 tanto 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 cumplido de 1 es el mismo que el número XOR de bits de conjunto completo.

Ahora que nos hemos entendido mutuamente, obtendremos two''s complement al restaurar todos los mordiscos al menos significativo en nuestro complemento .

data = ~data # one''s complement of data

Desafortunadamente, esto cambió todos los bits de nuestro número, por lo que solo tenemos que encontrar la forma de invertir los números que queremos. Podemos hacer eso con bit_shift ya que es la posición de bits de nuestro bit lo que necesitamos mantener. Entonces, al calcular el número de datos que puede contener cierta cantidad de bits, podemos hacer eso con 2**n para el mordisco 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

Entonces veamos la lógica en el 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 tenga este mismo problema y haya investigado su a ** para encontrar la solución. Tenga en cuenta que este código que escribí es código de frankenstein, que por eso tuve que explicarlo. Se podría hacer más bonito, si alguien quiere hacer mi código bonito, por favor, sea mi invitado.

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

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)

debería dar salida a esto: 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000

El complemento de dos resta (1<<bits) 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 complementos de 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 e.g., 8bit: 128-255 val = val - (1 << bits) # compute negative value return val # return positive value as is

Pasar de una secuencia 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í va desde 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)

>>> bits_in_word=12 >>> int(''111111111111'',2)-(1<<bits_in_word) -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 un complemento de dos bits de N). El complemento a dos del número se comporta como el negativo del número original en la mayoría de los ejercicios aritméticos, y puede coexistir con números positivos de forma natural.