用 XOR 檢查加法後是否有溢位

看 Python intobject.c 時看到的:

// intobject.c
static PyObject *
int_add(PyIntObject *v, PyIntObject *w)
{
    register long a, b, x;
    CONVERT_TO_LONG(v, a);
    CONVERT_TO_LONG(w, b);
    x = a + b;
    if ((x^a) >= 0 || (x^b) >= 0)
        return PyInt_FromLong(x);
    return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}

上面這段的

if ((x^a) >= 0 || (x^b) >= 0)

是在檢查是否有溢位, 看一陣子才想通, 概念如下:

• 兩個正數相加變成負數表示溢位
• 兩個負數相加變成正數也表示溢位
• 除了這兩者外沒有其它情況
• 綜合上述的條件, 可以簡化成: 兩數相加後的正負號和原本兩者都不同 <---> 溢位
• 目前 CPU 都採用二補數系統, 最高 bit 可看作是 sign bit
• XOR 剛好可以滿足簡化的條件, 其它 bit 無關緊要, 運算完看 sign bit 即可

位元運算的世界真神奇啊, 可以省下不少工。