"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

是的。名称是减法模 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)。这对你来说可能不是问题，但最好注意这一点，因为它可能会咬你。

"Symmetrical difference" 对于无符号整数 - 假定翻转

"Symmetrical difference" for unsigned ints - assumed rollover

c++

stl

integer-overflow

subtraction

underflow