负整数的 Python 表示

Question

>>> 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。是什么导致转换为有符号整数？

谢谢!

Answer 1

TLDR； 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 必须为各种目的提供按位运算。我们来看看the code中的评论:

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

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

为了在位运算中处理负整数，CPython 使用二进制补码(实际上，这是一个二进制补码，但我不详细介绍)。但请注意“符号规则”(名字是我的):结果的符号是应用于数字符号的按位运算符。更准确地说，如果 nega <op> negb == 1 ，结果为负(negx = 1 为负，0 为正)。 Simplified code:

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

二进制格式

另一方面，格式化程序不执行二进制补码，即使是二进制表示:format_long_internal 调用 long_format_binary 并删除两个前导字符，但保留符号。参见 the code:

 /* 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 为基数的数字 preceded by the sign。

    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 为负数。因此，它在逻辑与之前被逐位替换为它的二进制补码。您预计结果会变成负数，但请记住“符号规则”:

>>> 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 异或。结果是 0b11 ( 3 )。你取一元补码，又是 0b11111111111111111111111111111100，但这次符号是负数:

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

因此，如您所料，结果被取反并得到负号。

结论:我想没有完美的解决方案可以让任意长有符号数和提供按位运算，但文档并没有详细说明所做的选择。