c++ - “Symmetrical difference”，用于无符号整数-假定翻转

Question

我做了一个简单的函数，称为symmetricDelta()，它“对称地”计算value和previous之间的差异。我的意思是:考虑一个数字行，例如0到ULLONG_MAX，在此处连接数字线的左右两端...要确定“对称”增量，如果value - previous小于跨度的一半，则假定变化为正，否则假定变化为负，我们把数字线包起来。
在下面查看uint64_t的简单版本:

int64_t symmetricDelta(uint64_t value, uint64_t previous) {
    if (value-previous < (1ULL << 63)) {
        uint64_t result = value - previous;
        return result;
    } else {
        uint64_t negativeResult = previous - value;
        return -1 * negativeResult;
    }
}

用法:

    uint64_t value = ULLONG_MAX;
    uint64_t previous = 0;

    // Result: -1, not UULONG_MAX
    cout << symmetricDelta(value, previous) << endl;

演示: https://onlinegdb.com/BJ8FFZgrP
其他值示例，为简单起见，假定使用 uint8_t版本:

symmetricalDifference(1, 0) == 1
symmetricalDifference(0, 1) == -1
symmetricalDifference(0, 255) == 1
symmetricalDifference(255, 0) == -1
symmetricalDifference(227, 100) == 127
symmetricalDifference(228, 100) == -128

我的问题是:我所说的“对称减法”是否有“正式”名称？感觉好像已经在C++ STL中实现了，但是我什至不知道要搜索什么。

Answer 1

是。名称为modulo 2^64减法。这与您的机器按照指令执行的操作相同

int64_t symmetricDelta(uint64_t value, uint64_t previous) {
    return (int64_t)(value-previous);
}

在C和C++中，无符号算术被定义为环绕，从而将可表示数字范围的末端有效地连接成一个圆。这是带符号整数的2补码表示法的基础:您的CPU只需声明数字圆的一半即可解释为负数。这部分是无符号的上部， -1对应于最大可表示的无符号整数。只是因为 0在圆上是下一个。

Side note:
This allows the CPU to use the exact same circuitry for signed and unsigned arithmetic. The CPU only provides an add instruction that is used irrespective of whether the numbers should be interpreted as signed or unsigned. This is true for addition, subtraction and multiplication, they all exist as sign-ignorant instructions. Only the division is implemented in a signed and an unsigned variant, as are the comparison instructions / the flag bits that the CPU provides.

Side note 2:
The above is not fully true, as modern CPUs implement saturating arithmetic as part of their vector units (AVX etc.). Because saturating arithmetic means clipping the result to the ends of the representable range instead of wrapping around, this clipping depends on where the circle of numbers is assumed to be broken. As such, saturating arithmetic instructions typically exist in signed and unsigned variants.

End of the needless background rambling...

因此，当您以无符号表示形式减去两个数字时，结果就是从子代数到减数所必须采取的无符号步数。通过将结果重新解释为有符号整数，您可以将一条长路径(绕圆的一半以上)解释为相反方向上的相应短路径。

有一个陷阱: 1 << 63无法表示。它正好位于与零相对的数字圆的另一侧，并且由于设置了其符号位，因此将其解释为 -(1 << 63)。如果您尝试取反它，则位模式不会改变一位(就像 -0 == 0一样)，因此您的计算机会愉快地声明 - -(1 << 63) == -(1 << 63)。这可能对您来说不是问题，但是最好意识到这一点，因为它可能会咬住您。