Два дополнения в Python

Question

Существует ли в python встроенная функция, которая преобразует двоичную строку, например '111111111111', в целое число дополнения до двух -1?

Answer 1

Дополнение к двум вычитается из (1<<bits), если старший бит равен 1. Взяв, например, 8 битов, это дает диапазон от 127 до -128.

Функция для дополнения до двух целых ...

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

Переход от двоичной строки особенно прост ...

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

Немного более полезным для меня является использование шестнадцатеричных значений (32 бита в этом примере) ...

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

Answer 2

Он не встроен, но если вам нужны числа необычной длины, вы можете использовать модуль bitstring .

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

Один и тот же объект может быть эквивалентно создан несколькими способами, включая

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

Он просто ведет себя как строка битов произвольной длины и использует свойства для получения различных интерпретаций:

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

Answer 3

Начиная с Python 3.2, есть встроенные функции для манипулирования байтами: https://docs.python.org/3.4/library/stdtypes.html#int.to_bytes.

Объединив to_bytes и from_bytes, вы получите

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)

Проверка:

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

Для более старых версий Python ответ travc хорош, но он не работает для отрицательных значений, если вы хотите работать с целыми числами вместо строк. Функция дополнения двух, для которой f (f (val)) == val является истинной для каждого val, равна:

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

Answer 4

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

Это работает, потому что:

Двойное дополнение двоичного число определяется как значение получается путем вычитания числа от большой степени двух (в частности, от 2 ^ N для N-бита два дополнения). Двое дополнение числа тогда ведет себя как негатив оригинала число в большинстве арифметики, и это может сосуществовать с положительными числами в естественным путем.

Answer 5

Это даст вам эффективное дополнение к двум, используя побитовую логику:

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)

Как это работает:

Сначала мы удостоверимся, что пользователь передал нам значение, которое находится в пределах диапазона предоставленного диапазона битов (например, кто-то дает нам 0xFFFF и указывает 8 бит). Другим решением этой проблемы было бы побитовое И (&) значение с (2 ** bitWidth) -1

Чтобы получить результат, значение сдвигается на 1 бит влево. Это перемещает MSB значения (бит знака) в положение, которое должно быть добавлено с помощью 2**bitWidth. Когда знаковый бит равен 0, вычитаемое значение становится равным 0, а результат равен value - 0. Когда знаковый бит равен «1», вычитаемое значение становится 2**bitWidth, а результат равен value - 2**bitWidth

Пример 1: если параметры имеют значение = 0xFF (255d, b11111111) и bitWidth = 8

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

Пример 2. Если параметры имеют значение = 0x1F (31d, b11111) и bitWidth = 6

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

Пример 3: значение = 0x80, bitWidth = 7

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

Пример 4: значение = 0x80, bitWitdh = 8

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

Теперь, используя то, что уже опубликовали другие, передайте вашу цепочку битов в int (bitstring, 2) и передайте в параметр значения метода twos_complement.

Answer 6

Пара реализаций (просто иллюстрация, не предназначенная для использования):

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

Answer 7

Нет, встроенной функции, которая преобразует двоичные строки в два дополнения в десятичные числа.

Простая пользовательская функция, которая делает это:

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)

Обратите внимание, что эта функция не принимает битовую ширину в качестве параметра, вместо этого положительные входные значения должны указываться с одним или несколькими начальными нулевыми битами.

Примеры:

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

Answer 8

, если кому-то тоже нужно обратное направление:

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)

должно вывести это: 0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000

Answer 9

Поскольку erikb85 повысил производительность, вот ответ travc против Скотта Гриффитса :

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, как найдено в другом вопросе , почти на порядок медленнее, чем int. Но, с другой стороны, трудно превзойти простоту - я преобразую uint в битовую строку, затем в int; вам придется усердно работать , а не , чтобы понять это, или найти где-нибудь, чтобы внести ошибку. И, как следует из ответа Скотта Гриффитса, у класса гораздо больше гибкости, что может быть полезно для того же приложения. Но с третьей стороны, ответ travc проясняет, что на самом деле происходит - даже новичок должен быть в состоянии понять, что означает преобразование из неподписанного int в дополнение с 2s, подписанное int, просто из чтения 2 строк кода.

Во всяком случае, в отличие от другого вопроса, который был о непосредственном манипулировании битами, этот вопрос посвящен арифметике с целыми числами фиксированной длины, просто странного размера. Так что я думаю, если вам нужна производительность, это возможно потому, что у вас есть целая куча этих вещей, поэтому вы, вероятно, хотите, чтобы она была векторизована. Адаптация ответа 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

Сейчас:

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

Возможно, вы могли бы справиться с этим с помощью пользовательского кода на C, но вам, вероятно, не обязательно.

Answer 10

Хорошо, у меня возникла эта проблема с алгоритмом сжатия uLaw с PCM тип файла wav . И вот что я обнаружил, так это то, что дополнение к двум делает своего рода отрицательное значение некоторого двоичного числа , как можно увидеть здесь . И после консультации с wikipedia я счел это верным.

Парень объяснил это тем, что нашел least significant bit и перевернул все после него. Должен сказать, что все вышеперечисленные решения не сильно мне помогли. Когда я попробовал 0x67ff, он дал мне какой-то результат вместо -26623. Теперь решения могли бы сработать, если бы кто-то знал, что least significant bit сканирует список данных, но я не знал, так как данные в PCM различаются. Итак, вот мой ответ:

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

Теперь, поскольку код не читается, я проведу вас через эту идею.

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

Это просто любое шестнадцатеричное значение, мне нужно было проверить, чтобы быть уверенным, но в целом это может быть что угодно в диапазоне int . Поэтому, чтобы не зацикливаться на целой связке 65535 значений short integer, может быть, я решил разделить ее на nibbles (4 бита). Это можно сделать так, если вы раньше не использовали bitwise operators.

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 

Итак, мы ищем least significant bit, поэтому здесь достаточно min(valid_nibble ). Здесь мы получили место, где находится первый активный (с установленным битом) клев. Теперь нам просто нужно найти, где в нужном клеве наш первый установленный бит.

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

---

Теперь мне нужно кое-что прояснить, поскольку видение ~ и ^ может сбить с толку людей, которые к этому не привыкли:

XOR: ^: 2 номера необходимы

Эта операция довольно нелогична: для каждых 2 битов она сканирует, если оба равны 1 или 0, это будет 0, для всего остального 1.

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

И еще один пример:

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

1's complement: ~ - другой номер не требуется

Эта операция переворачивает каждый бит числа. Это очень похоже на то, что мы ищем, но не оставляет младший значащий бит .

0b10110  
~  
0b01001

И как мы можем видеть здесь, комплимент 1 такой же, как и полный бит числа XOR.

---

Теперь, когда мы поняли друг друга, мы получим two's complement, восстановив все биты до младший значащий бит в в дополнение .

data = ~data # one's complement of data 

Это, к сожалению, перевернуло все биты в нашем номере, поэтому нам просто нужно найти способ перевернуть числа, которые мы хотим. Мы можем сделать это с bit_shift, так как это битовая позиция нашего бита, которую мы должны сохранить. Таким образом, при вычислении количества данных, которое может содержать некоторое количество битов, мы можем сделать это с помощью 2**n, а для клева мы получаем 16, поскольку мы вычисляем 0 в значениях битов.

2**4 = 16 # in binary 1 0000 

Но нам нужны байты после 1, чтобы мы могли использовать это, чтобы уменьшить значение на 1, и мы можем получить.

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

Итак, давайте рассмотрим логику в конкретном примере:

 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

Я надеюсь, что это помогло бы вам или любому новичку, у которого была такая же проблема, и исследовали их ** поиск решения. Имейте в виду, что этот код, который я написал, является кодом Франкенштейна, поэтому я должен был объяснить это. Это может быть сделано красивее, если кто-то хочет сделать мой код красивым, пожалуйста, будьте моим гостем.