Python Битовые инверсные биты без переворачивания

Question

При использовании обратных питонов ~ кажется, что биты не перевернуты так, как я ожидал. Я полагаю, что путаница заключается в моем понимании того, как python хранит числа, используя комплимент 2.

myInt = 5 #101
inverse = ~myInt
print(bin(inverse))

Вывод: -0b110

Ожидается: -0b010 или -0b10

Answer 1

Это не проблема с оператором ~, который делает то, что должен, а с функцией bin, которую вы используете для отображения результатов.

В Python, как и в большинстве компьютерных систем, отрицательные целые числа хранятся внутри в двоичном представлении «два дополнения». Это означает, что -1 представлен последовательностью всех 1 битов, и каждое нижнее целое число изменяет это значение с помощью нормальных правил вычитания целых чисел. Таким образом, -2 формируется путем вычитания 1 из -1, и вы получаете набор из 1 битов, за которым следует ноль в качестве последнего бита.

Вот некоторые числа и двоичный код дополнения их двух 4-битные представления:

 0 : 0000
 1 : 0001
 2 : 0010
 5 : 0101
-1 : 1111  # this is ~0
-2 : 1110  # this is ~1
-3 : 1101  # this is ~2
-6 : 1010  # this is ~5

В отличие от многих других языков, целые числа Python не имеют заранее определенной длины в битах. Они не 16- или 32-битные, как целые числа short и long в C. Скорее они имеют динамический размер, с добавлением большего количества битов по мере необходимости для представления больших и больших чисел. Это вызывает сложную ситуацию, когда вам нужно представлять двоичные цифры в виде текста (как это делает функция bin). Если вы знали, что ваш номер использует только 16 бит, вы могли бы каждый раз записывать 16-значную строку, но для динамически изменяемого числа необходимо другое решение.

И действительно, Python делает что-то другое в bin функция. Положительные числа записываются с наименьшим количеством битов, необходимых для представления их значения. И отрицательные числа записываются не в дополнение к двум (как они фактически кодируются внутри), а вместо этого, ставя знак минус перед битовым представлением их абсолютного значения.

Таким образом, вы получаете Таблица, подобная этой, где побитовые дополнения не очевидны:

 0 :    0b0
 1 :    0b1
 2 :   0b10
 5 :  0b101
-1 :   -0b1
-2 :  -0b10
-3 :  -0b11
-6 : -0b110

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

MY_MAXINT = 2**4
for v in [0,1,2,5,-1,-2,-3,-6]:
    if v < 0:
        v += MY_MAXINT
    print(format(v, '04b'))

Answer 2

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

Если вы перевернете эту логику c, инвертирование двоичного представления сведет на нет значение и вычтет единицу. Таким образом, обратное значение 5 действительно должно быть -6.

~5                                                                                                                                                                                                                                  
# -6

Поскольку Python не использует фиксированное число битов для каждого целого числа, нет способа показать все ведущие нули (там бесконечное число). Таким образом, вместо этого стоит отрицательный знак впереди, -0b110 для -6.

Выберите любое фиксированное число битов, и вы можете записать двоичное число без отрицательного числа. Например, с 8 битами (один байт) это будет 1111 1010, то есть обратная величина, которую вы ожидали.

Answer 3

Вы правы - это поведение связано с тем, как Python сохраняет отрицательные числа в twos-дополнении . За кулисами, отрицая число, добавляя (эффективно) бесконечный список ведущих к двоичному представлению. Следовательно, хотя bin(6) равно 0b110, bin(-6) фактически равно 0b010 (вы можете убедиться в этом, заметив, что bin(-6 & 7) = 0b010.

Это означает, что использование ~ делает две вещи; оно переворачивается первый бит двоичного представления, а затем снова переворачивает все биты.

Answer 4

Поскольку Python имеет целые числа произвольного размера со знаком, концептуально они расширяются до бесконечности. Когда мы инвертируем биты 0b101, мы получаем 0b010, но расширение знака также переворачивается: число начинается с бесконечности 1 с, а не 0 с. И это 1111111....1010 значение равно -6, а не -2, потому что значение «все единицы» будет равно -1, а затем мы уберем 4 и 1 биты.

В общем, ~x для Python целое число равно -x - 1 (эквивалентно, -(x+1)). Это редко полезная операция для Python кода, но вы никогда не знаете:)