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?
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)
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
>>> 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.
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
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
- 0xFF - int ((0xFF << 1) & 2 ** 8)
- 0xFF - int ((0x1FE) & 0x100)
- 0xFF - int (0x100)
- 255 - 256
- -1
Beispiel 2: Wenn die Parameter value = 0x1F (31d, b11111) und bitWidth = 6 sind
- 0x1F - int ((0x1F << 1) & 2 ** 6)
- 0x1F - int ((0x3E) & 0x40)
- 0x1F - int (0x00)
- 31 - 0
- 31
Beispiel 3: Wert = 0x80, Bitbreite = 7
ValueError: Value: 128 out of range of 7-bit value.
Beispiel 4: Wert = 0x80, BitWitdh = 8
- 0x80 - int ((0x80 << 1) & 2 ** 8)
- 0x80 - int ((0x100) & 0x100)
- 0x80 - int (0x100)
- 128 - 256
- -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.
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
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.
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
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
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'
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
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
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.