用 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 即可
位元運算的世界真神奇啊, 可以省下不少工。

留言

這個網誌中的熱門文章

(C/C++ ) 如何在 Linux 上使用自行編譯的第三方函式庫

熟悉系統工具好處多多

virtualbox 使用 USB 裝置