时间戳

首页 > 解决方案 > 无符号整数的“对称差” - 假设翻转

c++ - 无符号整数的“对称差” - 假设翻转

问题描述

我做了一个简单的函数，我调用symmetricDelta()它计算value和previous“对称”之间的增量。我的意思是：考虑从 eg0到的数轴ULLONG_MAX，您连接数轴的左端和右端...要确定“对称”增量，如果value - previous小于一半，则假设变化为正跨度，否则假设变化是负的，我们环绕数字线。

请参阅下面的 s 的简单版本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 中实现的那种东西，但我什至不知道要搜索什么......

标签： c++stlsubtractioninteger-overflowunderflow

解决方案

是的。名称是减法模2^64。它与您的机器对指令所做的相同

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

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

旁注：
这允许 CPU 使用完全相同的电路进行有符号和无符号运算。CPU 仅提供一条add指令，无论数字应解释为有符号还是无符号，都可以使用该指令。加法、减法和乘法也是如此，它们都以无符号指令的形式存在。只有除法是在有符号和无符号变体中实现的，比较指令/CPU 提供的标志位也是如此。

旁注 2：
上述内容并不完全正确，因为现代 CPU 将饱和算术作为其矢量单元（AVX 等）的一部分。因为饱和算术意味着将结果剪裁到可表示范围的末端而不是环绕，所以这种剪裁取决于假设数字圈被破坏的位置。因此，饱和算术指令通常存在于有符号和无符号变体中。

结束不必要的背景漫谈……

因此，当您在无符号表示中减去两个数字时，结果是您必须采取的无符号步数才能从减数到达被减数。通过将结果重新解释为有符号整数，您将一条长路线（绕圆超过一半）解释为相反方向的相应短路线。

有一个陷阱：1 << 63不可表示。它正好在从零开始的数圈的另一侧，并且由于设置了它的符号位，所以它被解释为-(1 << 63)。如果您尝试否定它，则位模式不会改变一位（就像-0 == 0），因此您的计算机会愉快地声明- -(1 << 63) == -(1 << 63). 这对你来说可能不是问题，但最好意识到这一点，因为它可能会咬你。

推荐阅读