Zweierkomplement in Python

Gibt es eine eingebaute Funktion in Python, die eine binäre Zeichenfolge, zum Beispiel ‘111111111111’, in die Zweierkomplement ganzzahlig -1?

Das Zweierkomplement wird abgezogen (1<<bits) wenn das höchste Bit 1 ist. Nimmt man zum Beispiel 8 Bits, ergibt dies einen Bereich von 127 bis -128.

Eine Funktion für das Zweierkomplement eines Ganzzahl…

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ären Zeichenfolge zu gehen ist besonders einfach …

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

Etwas nützlicher für mich ist es, von Hex-Werten (in diesem Beispiel 32 Bit) auszugehen …

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 Zahlen mit ungewöhnlicher Länge wünschen, können Sie die verwenden Bitfolge Modul.

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

Dasselbe Objekt kann äquivalent auf verschiedene Arten erstellt werden, einschließlich

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

Es verhält sich einfach wie eine Reihe von Bits 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

Seit Python 3.2 gibt es eingebaute Funktionen zur Byte-Manipulation: 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)

Überprüfen:

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

Für ältere Python-Versionen ist die Antwort von travc gut, aber sie funktioniert nicht für negative Werte, wenn man mit ganzen Zahlen statt mit Strings arbeiten möchte. Eine Zweierkomplementfunktion, für die f(f(val)) == val für jeden val 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

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

Das funktioniert, weil:

Das Zweierkomplement einer Binärzahl ist definiert als der Wert, der durch Subtrahieren der Zahl von einer großen Zweierpotenz (insbesondere von 2^N für ein N-Bit-Zweierkomplement) erhalten wird. Das Zweierkomplement der Zahl verhält sich dann in den meisten Arithmetiken wie das Negative der ursprünglichen Zahl und kann auf natürliche Weise mit positiven Zahlen koexistieren.

Dadurch erhalten Sie das Zweierkomplement effizient mit bitweiser Logik:

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 im Bereich des bereitgestellten Bitbereichs liegt (z. B. gibt uns jemand 0xFFFF und spezifiziert 8 Bits). Eine andere Lösung für dieses Problem wäre das bitweise UND (&) 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 Werts (das Vorzeichenbit) in die Position, mit der anded werden soll 2**bitWidth. 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 – Ganzzahl (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 – Ganzzahl (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 – Ganzzahl ((0x100) & 0x100)
3. 0x80 – int(0x100)
4. 128 – 256
5. -128

Verwenden Sie nun das, was andere bereits gepostet haben, und übergeben Sie Ihren Bitstring an int(bitstring,2) und an den Wertparameter der twos_complement-Methode.

Ein paar Implementierungen (nur eine Illustration, nicht für den Gebrauch 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

Nein, es gibt keine eingebaute Funktion, die konvertiert Zweierkomplement binäre Zeichenfolgen in Dezimalzahlen.

Eine einfache benutzerdefinierte Funktion, die dies tut:

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 nimmt, stattdessen müssen positive Eingangswerte mit einem oder mehreren führenden Nullbits 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