用有符号的long long减去无符号的unsigned long long后得到的结果是有符号的吗？

Question

假设我有以下两种类型：

typedef unsigned long long uint64;
typedef signed long long sint64;

我有以下这些变量：

uint64 a = ...;
uint64 b = ...;
sint64 c;

我希望从a中减去b并将结果赋值给c，如果差的绝对值大于2^63，那么它将会回绕（或未定义），这是可以接受的。但对于绝对差小于2^63的情况，我希望结果是正确的。

以下是三种方式之一：

c = a - b; // sign conversion warning ignored

c = sint64(a - b);

c = sint64(a) - sint64(b);

哪些是按照标准保证可用的？（为什么/如何？）

- Andrew Tomazos

---

请参考以下相关问题：当二进制运算符两侧的符号不同时，促销规则如何工作？ - ildjarn

Answer 1

这三个函数都无法工作。第一个函数在差值为负数时（无论绝对值如何）失败，第二个与第一个相同，第三个如果任何操作数太大则失败。

没有条件语句是不可能实现的。

c = b < a? a - b : - static_cast< sint64 >( b - a );

基本上，unsigned 类型使用模数算术而没有任何符号位。它们不知道它们已经绕过了，语言规范也没有将绕过与负数识别。此外，分配超出有符号整数变量范围的值会导致实现定义的潜在无意义结果（整数溢出）。

考虑一台没有硬件用于转换本机负整数和二进制补码的机器。它可以使用按位取反和本机二进制补码加法执行二进制补码减法。 (可能很奇怪，但这是C和C++当前要求的。) 然后，语言让程序员自己来转换负值。唯一的方法是对正值取反，这需要计算出的差异是正的。所以...

最好的解决方案是避免在第一次尝试将负数表示为大正数。

编辑：我忘记了之前的强制类型转换，这将产生一个大的无符号值，等效于其他解决方案！

- Potatoswatter

Answer 2

Potatoswatter的回答可能是最实际的解决方案，但“没有分支就无法实现”对我来说就像对公牛挥舞的红布一样。如果您的假设系统实现了未定义的溢出/转换操作，那么我的假设系统通过杀死小狗来实现分支。

所以我不完全了解标准会说什么，但这个怎么样：

sint64 c,d,r;
c = a >> 1;
d = b >> 1;
r = (c-d) * 2;
c = a & 1;
d = b & 1;
r += c - d;

我用了相当冗长的方式来写它，以便清楚地表明各个操作，但留下了一些隐式转换。有未定义的内容吗？

Steve Jessop正确指出，在差值恰好为2^63-1的情况下，这确实会失败，因为在减去1之前，乘法已经溢出了。

所以这里有一个更加丑陋的版本，应该涵盖所有的下溢/上溢条件：

sint64 c,d,r,ov;
c = a >> 1;
d = b >> 1;
ov = a >> 63;
r = (c-d-ov) * 2;
c = a & 1;
d = b & 1;
r += ov + ov + c - d;

- JasonD

---

我比较熟悉C语言而不是C++，但在C语言中，负数的左移操作是未定义的（C99-C11）或者可以说是实现定义的（C90）。对于有符号数进行左移操作，如果移位后的值超出了该类型的范围，也是未定义的（你的代码避免了这种情况）。 - Pascal Cuoq

是的，我认为将符号位移动可能会导致未定义行为，但我找不到任何清晰的参考资料。 - JasonD

如果在C++中前者未定义，您可以随时将<< 1更改为* 2。 - Pascal Cuoq

我们可以进行额外的位操作，只在最高位被设置的情况下减去1 / 加上2，避免溢出和下溢。 - JasonD

@Potatoswatter 我并没有激动 :) 我不认为有人会把我的答案误认为是比你的更好，甚至是更明智的选择。然而，虽然我的答案显然效率低下，但我没有对有符号数进行任何位运算。所有的位运算都是在无符号值上进行的，并且计算是使用有符号值完成的。 - JasonD

Answer 3

如果差的绝对值大于2^63，那么它将包装（或未定义），这很好。但是对于差的绝对值小于2^63的情况，我希望结果是正确的。

然后，你提出的所有三个表示法都可以使用，假设采用传统的架构。显著的区别在于第三个表示法`sint64(a) - sint64(b)`在差不可表示时调用未定义的行为，而前两个则保证会进行包装（无符号算术溢出保证会进行包装，并且从无符号转换为有符号是实现定义的，而有符号算术溢出则是未定义的）。

- Pascal Cuoq

---

三种都不行。第一种如果差值为负数（无论绝对值如何），则失败；第二种与第一种相同；第三种如果任一操作数过大，则失败。 - Potatoswatter

@Potatoswatter 我们可能对问题的理解有所不同。我认为这个问题是关于计算a和b之间差值的，而不是它们差值的绝对值。如果这是目标，那么sint64(a - b)可以实现，即使无符号减法a - b发生了溢出。 - Pascal Cuoq

“Wrapping around results in a number that cannot be represented by the signed type” 不一定。对于 a==2 和 b==3，会发生 wrap-around，但结果是一个实现定义的数字，可以转换为 -1。 - Pascal Cuoq

你刚刚定义了实现吗？;v) - 但你部分正确；结果是实现定义的（在这个问题的语境中意味着无用）。然而，对于溢出整数类型的浮点-整数转换，确实会发生未定义行为。 - Potatoswatter

问题是“哪些是标准保证能够工作的？（为什么/如何？）”，这不是一个实际问题。 - Potatoswatter