wake-up-neo.com

Zwei-Komplement in Python

Gibt es eine eingebaute Funktion in Python, die eine binäre Zeichenfolge, zum Beispiel '111111111111', in die two-Komplement-Ganzzahl -1 konvertiert? 

51
Jim

Das Zweierkomplement subtrahiert off (1<<bits), wenn das höchste Bit 1 ist. Wenn Sie beispielsweise 8 Bit verwenden, erhalten Sie einen Bereich von 127 bis -128.

Eine Funktion für zwei Komplemente eines 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

Von einer Binärzeichenfolge zu gehen ist besonders einfach ...

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

Ein bisschen nützlicher für mich sind Hex-Werte (in diesem Beispiel 32 Bit).

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

Es ist nicht eingebaut, aber wenn Sie ungewöhnliche Längenangaben wünschen, können Sie das Modul bitstring verwenden.

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

Dasselbe Objekt kann auf verschiedene Weise gleichwertig erstellt werden, einschließlich

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

Es verhält sich nur wie eine Bitfolge beliebiger Länge und verwendet Eigenschaften, um unterschiedliche Interpretationen zu erhalten:

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

Das funktioniert aus folgenden Gründen:

Das Zweierkomplement eines binären Anzahl ist als Wert definiert erhalten durch Abzug der Zahl aus einer großen Zweierpotenz (speziell ab 2 ^ N für ein N-Bit. Zwei Komplement). Die zwei sind Komplement der Nummer verhält sich dann wie das Negativ des Originals Zahl in den meisten Arithmetik, und es kann koexistieren mit positiven Zahlen in einem natürliche Weise.

8
John La Rooy

Seit Python 3.2 gibt es integrierte Funktionen für die Byte-Bearbeitung: https://docs.python.org/3.4/library/stdtypes.html#int.to_bytes .

Durch die Kombination von to_bytes und from_bytes erhalten Sie

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)

Prüfen:

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

In älteren Versionen von Python ist die Antwort von travc gut, aber es funktioniert nicht für negative Werte, wenn man mit Ganzzahlen anstelle von Strings arbeiten möchte. Eine Zweierkomplementfunktion, für die f(f(val)) == val für jeden Wert wahr ist, lautet:

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
8
Gaël Ecorchard

Dadurch erhalten Sie das Zweierkomplement mithilfe der bitweisen Logik effizient:

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)

Wie es funktioniert:

Zuerst stellen wir sicher, dass der Benutzer uns einen Wert übergeben hat, der sich innerhalb des Bereichs des angegebenen Bitbereichs befindet (z. B. gibt uns 0xFFFF und 8 Bits an). Eine andere Lösung für dieses Problem wäre das bitweise AND (&) des Werts mit (2 ** Bitbreite) -1 

Um das Ergebnis zu erhalten, wird der Wert um 1 Bit nach links verschoben. Dies verschiebt das MSB des Wertes (das Vorzeichenbit) in die Position, die mit 2**bitWidth zu verknüpfen ist. Wenn das Vorzeichenbit '0' ist, wird der Subtrahend 0 und das Ergebnis ist value - 0. Wenn das Vorzeichenbit '1' ist, wird der Subtrahend 2**bitWidth und das Ergebnis ist value - 2**bitWidth

Beispiel 1: Wenn die Parameter value = 0xFF (255d, b11111111) und bitWidth = 8 sind

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

Beispiel 2: Wenn die Parameter value = 0x1F (31d, b11111) und bitWidth = 6 sind

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

Beispiel 3: Wert = 0x80, Bitbreite = 7

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

Beispiel 4: Wert = 0x80, BitWitdh = 8

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

Übergeben Sie jetzt, was andere bereits gepostet haben, Ihre Bitkette in int (Bitstring, 2) und übergeben Sie sie an den value-Parameter der Methode twos_complement.

3
Tom Myddeltyn

Einige Implementierungen (nur eine Illustration, nicht zur Verwendung bestimmt):

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

Da erikb85 die Performance ansprach, ist hier travcs Antwort gegen 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 ist also, wie in der anderen Frage , fast eine Größenordnung langsamer als int. Andererseits ist die Einfachheit jedoch schwer zu schlagen: Ich konvertiere eine uint in eine Bit-Zeichenfolge und dann eine int. Sie müssten hart arbeiten not, um dies zu verstehen, oder um irgendwo einen Bug zu finden. Die Antwort von Scott Griffiths impliziert, dass die Klasse viel flexibler ist, was für dieselbe App nützlich sein könnte. Auf der dritten Seite macht die Antwort von travc klar, was tatsächlich passiert. Selbst ein Neuling sollte in der Lage sein zu verstehen, welche Konvertierung von einem unsignierten int in ein 2s-Komplement mit einem signierten int durch das Lesen von zwei Codezeilen erfolgt.

Im Gegensatz zu der anderen Frage, bei der es um das direkte Manipulieren von Bits ging, geht es in diesem Fall nur darum, mit Ints fester Länge zu rechnen, nur mit merkwürdig großen. Ich vermute also, wenn Sie Leistung brauchen, liegt dies wahrscheinlich daran, dass Sie eine ganze Reihe dieser Dinge haben, also möchten Sie, dass es vektorisiert wird. Anpassung von travc an 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

Jetzt:

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

Sie könnten das wahrscheinlich mit benutzerdefiniertem C-Code schlagen, aber Sie müssen es wahrscheinlich nicht.

1
abarnert

falls jemand auch die umgekehrte Richtung benötigt:

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)

sollte Folgendes ausgeben: __. 0111 __ 0110 __ 0101 __ 0100 __ 0011 __ 0010 __ 0001 __ 0000 __1111 __ 1110 __ 1110 __ 1101 __ .1100 1011 1010 1001 1000

Nein, es gibt keine eingebaute Funktion, die Zweierkomplement Binärzeichenfolgen in Dezimalzahlen umwandelt.

Eine einfache benutzerdefinierte Funktion, die dies ausführt:

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)

Beachten Sie, dass diese Funktion nicht die Bitbreite als Parameter verwendet, sondern positive Eingabewerte müssen mit einem oder mehreren führenden Null-Bits angegeben werden.

Beispiele:

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

Hier ist eine Version, um jeden Wert in einer Hex-Zeichenfolge in die Zweierkomplement-Version zu konvertieren.


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            
0

Ich verwende Python 3.4.0

In Python 3 haben wir einige Probleme mit der Datentyptransformation.

Also ... hier werde ich für diejenigen einen Tipp geben (wie ich), der viel mit Hex-Saiten funktioniert.

Ich nehme ein Hex-Datum und mache eine Ergänzung:

a = b'acad0109'

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

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

ergebnis = -1397948151 oder -0x5352fef7 oder '-0b10100110101001001111111011110111'

0
SnowBG

Leider gibt es keine eingebaute Funktion, um eine vorzeichenlose Ganzzahl in einen Zweierkomplementwert umzuwandeln. Wir können jedoch eine Funktion definieren, die bitweise Operationen verwendet:

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

Die erste bitweise-und -Operation wird verwendet, um negative Zahlen mit Vorzeichen zu erweitern (das höchstwertige Bit ist gesetzt), während das zweite Bit die restlichen 11 Bits erfasst. Dies funktioniert, da ganze Zahlen in Python als willkürliche Genauigkeits-Zwei-Komplement-Werte behandelt werden.

Sie können dies mit der Funktion int kombinieren, um eine Zeichenfolge aus Binärziffern in die vorzeichenlose Ganzzahlform zu konvertieren und sie dann als vorzeichenbehafteten 12-Bit-Wert zu interpretieren.

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

Eine Nice-Eigenschaft dieser Funktion ist, dass sie idempotent ist. Der Wert eines bereits signierten Werts wird also nicht geändert.

>>> s12(-1)
-1
0
dcoles

Dies funktioniert für 3 Bytes. Live Code ist hier

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
0
D.Deriso

Ok, ich hatte dieses Problem mit dem uLaw-Kompressionsalgorithmus mit PCM-WAV-Dateityp. Und ich habe herausgefunden, dass das Zweierkomplement gewissermaßen einen negativen Wert einer Binärzahl wie hier zu sehen ergibt. Und nach Rücksprache mit wikipedia hielt ich es für wahr. 

Der Kerl erklärte es als das Finden von least significant bit und das Umblättern danach. Ich muss sagen, dass mir alle diese Lösungen nicht viel gebracht haben. Als ich 0x67ff anprobierte, gab es mir ein anderes Ergebnis als -26623. Jetzt haben Lösungen möglicherweise funktioniert, wenn jemand gewusst hat, dass der least significant bit eine Liste von Daten durchsucht, aber ich wusste nicht, da die Daten in PCM variieren. Hier ist meine Antwort:

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

Da Code nicht lesbar ist, werde ich Sie durch die Idee führen. 

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

Dies ist nur ein beliebiger Hexadezimalwert. Ich brauchte einen Test, um sicherzugehen, aber im Allgemeinen kann es sich um einen beliebigen Bereich im Bereich von int handeln. Um nicht eine ganze Reihe von 65535 -Werten zu durchlaufen, short integer kann ich mich dazu entscheiden, sie durch Nibbles (4 Bits) zu teilen. Wenn Sie bitwise operators noch nicht verwendet haben, können Sie dies wie folgt tun.

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 

Wir suchen also nach least significant bit, so dass hier die min(valid_nibble ) ausreicht. Hier haben wir den Ort gefunden, an dem sich das erste aktive (mit gesetztem Bit) Nibbeln befindet. Jetzt müssen wir nur noch herausfinden, wo in dem gewünschten Nibble unser erstes festes Bit liegt. 

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

Jetzt muss ich etwas klären, seit ich gesehen habe, dass ~ und ^ Leute verwirren können, die das nicht gewohnt sind: 

XOR : ^: Es sind 2 Nummern erforderlich 

Diese Operation ist ein bisschen unlogisch. Für jeweils 2 Bits wird gescannt, wenn beide entweder 1 oder 0 sind, wird es 0 sein, für alles andere 1. 

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

Und noch ein Beispiel: 

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

1's complement : ~ - benötigt keine andere Nummer 

Diese Operation kippt jedes Bit in einer Zahl. Es ist dem, was wir suchen, sehr ähnlich, hinterlässt jedoch nicht das niederwertigste Bit

0b10110  
~  
0b01001

Und wie wir hier sehen können, ist das Kompliment von 1 das Gleiche wie die Anzahl XOR der vollen Mengen. 


Nun, da wir uns gegenseitig verstanden haben, werden wir two's complement erhalten, indem wir alle Bisse auf niederwertigstes Bit in jemandes Komplement wiederherstellen. 

data = ~data # one's complement of data 

Leider haben wir alle Bits in unserer Nummer umgedreht, so dass wir nur einen Weg finden müssen, um die gewünschten Zahlen zurückzudrehen. Wir können das mit bit_shift machen, da es eine Bitposition unseres Bits ist, die wir behalten müssen. Wenn wir also die Anzahl der Daten berechnen, die eine Anzahl von Bits enthalten kann, können wir dies mit 2**n tun, und für Nibble erhalten wir 16, da wir 0 in Bitwerten berechnen. 

2**4 = 16 # in binary 1 0000 

Aber wir brauchen die Bytes nach dem 1, damit wir den Wert um 1 verringern und erhalten können. 

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

Also lassen Sie uns die Logik in einem konkreten Beispiel sehen: 

 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

Ich hoffe, dass Ihnen oder jedem Neuling, der dasselbe Problem hatte, geholfen hat, und erörtert wurde, wie er die Lösung gefunden hat. Denken Sie daran, dass dieser Code, den ich schrieb, frankenstein code ist, warum ich ihn erklären musste. Es könnte schöner sein, wenn jemand meinen Code hübsch machen möchte, seien Sie bitte mein Gast. 

0
Danilo