Представление отрицательных целых чисел на Python

>>> x = -4
>>> print("{} {:b}".format(x, x))
-4 -100
>>> mask = 0xFFFFFFFF
>>> print("{} {:b}".format(x & mask, x & mask))
4294967292 11111111111111111111111111111100
>>> 
>>> x = 0b11111111111111111111111111111100
>>> print("{} {:b}".format(x, x))
4294967292 11111111111111111111111111111100
>>> print("{} {:b}".format(~(x ^ mask), ~(x ^ mask)))
-4 -100

Мне трудно понять, как Python представляет отрицательные целые числа, и, следовательно, как работают битовые операции. Я понимаю, что Python пытается подражать двум дополнениям, но с любым количеством бит. Поэтому обычно используют 32-битные маски, чтобы заставить Python устанавливать стандартный размер для целых чисел до операций с битами.

Как вы можете видеть в моем примере, -4 & 0xFFFFFFFF дает большое положительное число. Почему Python, кажется, читает это как целое без знака, вместо отрицательного числа из двух дополнений? Позже операция ~(x ^ mask), которая должна дать то же самое два бита бита дополнения, что и большой положительный, вместо этого дает -4. Что вызывает преобразование в подписанный int?

Спасибо!

Ответ 1

TL;DR; Целочисленный тип CPython хранит знак в определенном поле структуры. При выполнении побитовой операции CPython заменяет отрицательные числа их двумя дополнениями, а иногда (!) Выполняет обратную операцию (т.е. заменяет два дополнения отрицательными числами).

Битовые операции

Внутренним представлением целого числа является структура PyLongObject, которая содержит структуру PyVarObject. (Когда CPython создает новый PyLong объект, он выделяет память для структуры и косую пространство для цифр.) Что здесь дело в том, что PyLong имеет размеры: ob_size поле PyVarObject вложенной структуры содержит размер (в цифрах) целого числа (цифры 15 или 30 бит). Если целое число отрицательное, то этот размер минус количество цифр.

(Ссылки: https://github.com/python/cpython/blob/master/Include/object.h и https://github.com/python/cpython/blob/master/Include/longobject.h)

Как видите, внутреннее представление целого числа в CPython действительно далеко от обычного двоичного представления. Тем не менее, CPython должен предоставлять побитовые операции для различных целей. Давайте посмотрим на комментарии в коде:

static PyObject *
long_bitwise(PyLongObject *a,
             char op,  /* '&', '|', '^' */
             PyLongObject *b)
{
    /* Bitwise operations for negative numbers operate as though
       on a two complement representation.  So convert arguments
       from sign-magnitude to two complement, and convert the
       result back to sign-magnitude at the end. */

    /* If a is negative, replace it by its two complement. */
    /* Same for b. */
    /* Complement result if negative. */
}

Чтобы обработать отрицательные целые числа в побитовых операциях, CPython использует два дополнения (фактически, это два дополнения цифра за цифрой, но я не буду вдаваться в подробности). Но обратите внимание на "Правило знака" (имя мое): знак результата - побитовый оператор, применяемый к знакам чисел. Точнее, результат будет отрицательным, если nega <op> negb == 1, (negx= 1 для отрицательного, 0 для положительного). Упрощенный код:

switch (op) {
    case '^': negz = nega ^ negb; break;
    case '&': negz = nega & negb; break;
    case '|': negz = nega | negb; break;
    default: ...
}

Двоичное форматирование

С другой стороны, [format_long_internal](https://github.com/python/cpython/blob/master/Python/formatter_unicode.c#L839) форматирования не выполняет два дополнения, даже в двоичном представлении: [format_long_internal](https://github.com/python/cpython/blob/master/Python/formatter_unicode.c#L839) вызывает [long_format_binary](https://github.com/python/cpython/blob/master/Objects/longobject.c#L1934) и удалите два начальных символа, но оставьте знак. Смотрите код:

 /* Is a sign character present in the output?  If so, remember it
           and skip it */
        if (PyUnicode_READ_CHAR(tmp, inumeric_chars) == '-') {
            sign_char = '-';
            ++prefix;
            ++leading_chars_to_skip;
}

Функция long_format_binary не выполняет никаких двух дополнений: просто выведите число в базе 2, перед которым стоит знак.

    if (negative)                                                   \
        *--p = '-'; \

Ваш вопрос

Я буду следовать вашей последовательности REPL:

>>> x = -4
>>> print("{} {:b}".format(x, x))
-4 -100

Ничего удивительного, учитывая, что в форматировании нет двух дополнений, кроме знака.

>>> mask = 0xFFFFFFFF
>>> print("{} {:b}".format(x & mask, x & mask))
4294967292 11111111111111111111111111111100

Число -4 отрицательно. Следовательно, он заменяется двумя дополнениями перед логическим и, цифра за цифрой. Вы ожидали, что результат будет преобразован в отрицательное число, но поменяйте "Sign Rule":

>>> nega=1; negb=0
>>> nega & negb
0

Следовательно: 1. результат не имеет отрицательного знака; 2. результат не дополняется до двух. Ваш результат соответствует "правилу подписания", даже если это правило не кажется интуитивно понятным.

Теперь последняя часть:

>>> x = 0b11111111111111111111111111111100
>>> print("{} {:b}".format(x, x))
4294967292 11111111111111111111111111111100
>>> print("{} {:b}".format(~(x ^ mask), ~(x ^ mask)))
-4 -100

Опять же, -4 отрицателен, поэтому заменяется двумя дополнениями 0b11111111111111111111111111111100, затем 0b11111111111111111111111111111111 с 0b11111111111111111111111111111111. Результат 0b11 (3). Вы берете дополнение одинарное, то есть снова 0b11111111111111111111111111111100, но на этот раз знак отрицательный:

>>> nega=1; negb=0
>>> nega ^ negb
1

Следовательно, результат дополняется и получает отрицательный знак, как вы и ожидали.

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