Le complément de Two en Python

le complément de Two soustrait (1<<bits) si le bit le plus élevé est 1. En prenant 8 bits par exemple, cela donne une fourchette de 127 à 128.

Une fonction de complément à deux d'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

aller à partir d'une chaîne binaire est particulièrement facile...

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

un peu plus utile pour moi va des valeurs hex (32 bits dans cet exemple)...

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

il n'est pas intégré, mais si vous voulez des numéros de longueur inhabituels, vous pouvez utiliser le module bitstring .

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

le même objet peut être créé de plusieurs façons, y compris

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

il se comporte simplement comme une chaîne de bits de longueur arbitraire, et utilise des propriétés pour obtenir différentes interprétations:

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

>>> bits_in_word=12
>>> int('111111111111',2)-(1<<bits_in_word)
-1

cela fonctionne parce que:

le complément des deux d'un binaire le numéro est défini comme la valeur obtenu en soustrayant le nombre à partir d'une grande puissance de deux (plus précisément, à partir de 2^n Pour Un N-bit en complément à deux). Les deux le complément du nombre se comporte alors comme le négatif de l'original nombre dans la plupart des arithmétique, et il peut coexister avec des nombres positifs dans un de façon naturelle.

depuis Python 3.2, il y a des fonctions intégrées pour la manipulation des octets: https://docs.python.org/3.4/library/stdtypes.html#int.to_bytes .

en combinant to_bytes et from_bytes, vous obtenez

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)

Case:

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

pour les versions plus anciennes de Python, la réponse de travc est bonne mais elle ne fonctionne pas pour les valeurs négatives si l'on veut travailler avec des entiers au lieu de chaînes. Un fonction de complément de deux pour laquelle f (F (val)) = = val est vrai pour chaque val est:

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

quelques implémentations (juste une illustration, non destinée à être utilisée):

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

cela vous donnera le complément de deux efficacement en utilisant la logique 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)

Comment cela fonctionne:

tout d'abord, nous nous assurons que l'utilisateur nous a transmis une valeur qui est dans la plage de bits fournie (par exemple quelqu'un nous donne 0xFFFF et spécifie 8 bits) une autre solution à ce problème serait de bitwise et (&) la valeur avec (2*bitWidth)-1

pour obtenir le résultat, la valeur est décalée de 1 bit à la gauche. Cela déplace le MSB de la valeur (le bit de signe) en position pour être Andé avec 2**bitWidth . Lorsque le bit de signe est " 0 " la soustraction devient 0 et le résultat est value - 0 . Lorsque le bit de signe est '1' , le sous-tiret devient 2**bitWidth et le résultat est value - 2**bitWidth

exemple 1: si les paramètres sont valeur=0xFF (255d, b11111111) et bitWidth=8

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

exemple 2: Si les paramètres sont valeur=0x1F (31d, b11111) et bitWidth=6

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

exemple 3: Valeur = 0x80, bitWidth = 7

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

exemple 4: valeur = 0x80, bitWitdh = 8

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

maintenant, en utilisant ce que d'autres vous avez déjà posté, passez votre bitstring dans int (bitstring,2) et passez au paramètre de valeur de la méthode twos_complement.

depuis que erikb85 a évoqué la performance, voici réponse de travc contre 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

, bitstring est, comme on le trouve dans à la question , presque un ordre de grandeur inférieure à celle int . Mais d'un autre côté, il est difficile de battre la simplicité-je suis en train de convertir un uint en une chaîne de bits puis en un int ; il faudrait travailler dur pas pour comprendre ceci, ou pour trouver n'importe où pour introduire un bug. Et comme la réponse de Scott Griffiths l'indique, il y a beaucoup plus de flexibilité dans la classe qui pourrait être utile pour la même application. Mais d'un autre côté, la réponse de travc indique clairement ce qui se passe réellement-même un novice devrait être capable de comprendre ce que la conversion d'un int non signé à un 2S complement signed int signifie Juste de la lecture de 2 lignes de code.

en tout cas, contrairement à l'autre question, qui était sur la manipulation directe des bits, celui-ci est tout au sujet de faire l'arithmétique sur les longueurs fixes ints, juste étrangement de taille ceux. Donc je suppose que si vous avez besoin de performances, c'est probablement parce que vous avez tout un tas de ces choses, alors vous voudrez probablement à être vectorisé. Adaptation de la réponse de travc à 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

Maintenant:

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

vous pourriez probablement battre cela avec le code C personnalisé, mais vous ne devez probablement pas.

dans le cas où quelqu'un a besoin de la direction inverse aussi:

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)

devrait sortir ce: Zero cents onze Zero cents dix Zero cents un Zero cent Zero zero onze Zero zero dix Zero zero zero un Zero zero zero zero Mille cents onze Mille cents dix Mille cents un Mille cent Mille onze Mille dix Mille un 1000

Non, il n'y a pas de fonction intégrée qui convertisse le complément de two les chaînes binaires en décimales.

une fonction simple définie par l'utilisateur qui fait ceci:

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)

notez que cette fonction ne prend pas la largeur de bits comme paramètre, les valeurs d'entrée positives doivent être spécifiées avec un ou plusieurs bits zéro.

exemples:

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

j'utilise Python 3.4.0

en Python 3 nous avons quelques problèmes avec la transformation des types de données.

So... ici, je vais dire un conseil pour ceux (comme moi) qui fonctionne beaucoup avec des cordes hexagonales.

je vais prendre une donnée hexadécimale et la compléter:

a = b'acad0109'

compl = int(a,16)-pow(2,32)

result=hex(compl)
print(result)
print(int(result,16))
print(bin(int(result,16)))

résultat = -1397948151 ou -0x5352fef7 ou '-0b1010011010100101111111011110111'

malheureusement, il n'y a pas de fonction intégrée pour lancer un entier non signé à la valeur signée du complément de deux, mais nous pouvons définir une fonction pour le faire en utilisant des opérations bitwise:

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

le premier bit-and operation est utilisé pour signer-étendre les nombres négatifs (le bit le plus significatif est défini), tandis que le second est utilisé pour saisir les 11 bits restants. Cela fonctionne car les entiers en Python sont traités comme des valeurs de complément de precision two arbitraires.

vous pouvez alors combiner cela avec la fonction int pour convertir une chaîne de chiffres binaires dans la forme entière non signée, puis l'interpréter comme une valeur signée de 12 bits.

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

une belle propriété de cette fonction est qu'elle est idempotent, donc la valeur d'une valeur déjà signée ne changera pas.

>>> s12(-1)
-1

cela fonctionne pour 3 octets. Live code est ici

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 j'ai eu ce problème avec uLaw algorithme de compression avec PCM wav fichier de type . Et ce que j'ai découvert c'est que le complément de two fait en quelque sorte une valeur négative d'un nombre binaire comme on peut le voir ici .Et après avoir consulté wikipedia Je l'ai jugé vrai.

le gars l'a expliqué comme la conclusion least significant bit et le retournement tous les après. Je dois dire que toutes ces solutions ci-dessus ne m'aide pas beaucoup. Quand j'ai essayé sur 0x67ff il m'a donné un certain résultat off au lieu de -26623 . Maintenant les solutions peuvent avoir fonctionné si quelqu'un savait que le least significant bit est la liste de balayage de données mais je ne savais pas puisque les données dans PCM varie. Voici donc ma réponse:

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

puisque le code est illisible, je vais vous expliquer l'idée.

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

C'est juste n'importe quelle valeur hexadécimale, j'ai eu besoin de test pour être sûr mais en général il pourrait être n'importe quoi dans la gamme de int . Donc, pour ne pas boucler sur tout le tas de 65535 valeurs short integer peut avoir j'ai décidé de le diviser par nibbles (4 bits ). Cela peut être fait si vous n'avez pas déjà utilisé bitwise operators avant.

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 

donc nous cherchons least significant bit donc ici le min(valid_nibble ) suffira. Ici, nous avons obtenu l'endroit où le premier actif (avec sertie bits) grignoter. Maintenant, nous avons juste besoin de trouver où dans le grignotage désiré est notre premier bit fixé.

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

maintenant ici je dois clarifier quelque chose car voir ~ et ^ peut confondre les gens qui ne sont pas habitués à cela:

XOR : ^ : 2 numéros sont nécessaires

cette opération est un peu illogique, pour chaque 2 bits il scanne si les deux sont 1 ou 0 Il sera 0, pour tout le reste 1.

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

et un autre exemple:

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

1's complement : ~ - n'a pas besoin d'un autre numéro

cette opération fait basculer chaque morceau d'un nombre. Il est très similaire à ce que nous sommes après mais il ne laisse pas le bit le moins significatif .

0b10110  
~  
0b01001

et comme nous pouvons le voir ici le compliment de 1 est le même que le nombre XOR bits plein jeu.

maintenant que nous nous sommes compris, nous obtiendrons two's complement en rétablissant toutes les morsures à bit le moins significatif dans complément de l'un .

data = ~data # one's complement of data 

cela a malheureusement retourné tous les bits de notre Nombre, donc nous avons juste besoin de trouver un moyen de retourner les nombres que nous voulons. Nous pouvons faire cela avec bit_shift puisque c'est la position de bit de notre bit que nous devons garder. Ainsi, lors du calcul du nombre de données un certain nombre de bits peut tenir, nous pouvons le faire avec 2**n et pour nibble nous obtenons 16 puisque nous calculons 0 dans les valeurs de bits.

2**4 = 16 # in binary 1 0000 

mais nous avons besoin des octets après le 1 donc nous pouvons utiliser que pour diminuer la valeur de 1 et nous pouvons obtenir.

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

ainsi laisse voir la logique dans l'exemple concret:

 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

j'espère que cela vous a aidé ou n'importe quel débutant qui avait ce même problème et a fait des recherches sur leur a** trouver la solution. Avoir à l'esprit ce code que j'ai écrit est frankenstein code , que je pourquoi j'ai dû l'expliquer. Il pourrait être fait de plus beau, si quelqu'un veut faire mon code jolie s'il vous plaît être mon invité.

c'est beaucoup plus facile que tout ça...

pour X sur n bits: Comp = (-X) & (2**N - 1)

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