无符号整数减法是否定义了行为？

我曾经遇到过一个人，他似乎认为从另一个相同类型的整数中减去一个无符号整数是一个问题，而结果却是负数。因此，这样的代码是不正确的，即使它碰巧在大多数架构上工作。

unsigned int To, Tf;


To = getcounter();
while (1) {
Tf = getcounter();
if ((Tf-To) >= TIME_LIMIT) {
break;
}
}

这是我能找到的唯一与 C 标准相关的模糊引用。

涉及无符号操作数的计算永远不会溢出，因为 不能由结果无符号整数表示的结果 类型是减模的数目是一个比最大的 值，该值可以由结果类型表示。

我想人们可以把这个引号理解为，当正确的操作数更大时，在模截断数的上下文中，操作被调整为有意义的。

也就是说。

0x0000-0x0001 = = 0x10000-0x0001 = = = 0xFFFF

而不是使用依赖于实现的签名语义:

0x0000-0x0001 = = (未签名)(0 + -1) = = (0xFFFF 但也可以是0xFFFE 或0x8001)

Which or what interpretation is right? Is it defined at all?

133391 次浏览
小开
最佳答案

在无符号类型中产生负数的减法的结果是明确的:

  1. [ ... ]涉及无符号操作数的计算永远不会溢出, 因为不能由结果无符号整数类型表示的结果是 降低模的数，即大于可能的最大值的数 由结果类型表示。 (ISO/IEC9899:1999(E)6.2.5/9)

As you can see, (unsigned)0 - (unsigned)1 equals -1 modulo UINT_MAX+1, or in other words, UINT_MAX.

请注意，尽管它确实说过“涉及无符号操作数的计算永远不会溢出”，这可能会让你认为它只适用于超过上限的情况，但是对于句子的实际绑定部分，这是以 动力的形式表示的: “不能由结果无符号整数类型表示的结果是 降低模的数，即大于可能的最大值的数 由结果类型表示。”此短语不限于类型上限的溢出，同样适用于太低而无法表示的值。

小开

当您处理 没签名类型时，同余关系(也称为 “缠绕”行为)正在发生。要理解这个 同余关系，只需看看这些时钟:

enter image description here

9 + 4 = 1 (13模块12) ，所以在另一个方向是: 1-4 = 9(-3 M12)。在处理无符号类型时应用相同的原则。如果 结果类型是 unsigned，那么同余关系就发生了。

现在查看以下将结果存储为 unsigned int的操作:

unsigned int five = 5, seven = 7;
unsigned int a = five - seven;      // a = (-2 % 2^32) = 4294967294


int one = 1, six = 6;
unsigned int b = one - six;         // b = (-5 % 2^32) = 4294967291

当您想要确保结果是 signed时，然后将其存储到 signed变量中或将其强制转换为 signed。当你想得到数字之间的差异，并确保同余关系不会被应用，那么你应该考虑使用 stdlib.h中定义的 abs()函数:

int c = five - seven;       // c = -2
int d = abs(five - seven);  // d =  2

要非常小心，尤其是在写条件的时候，因为:

if (abs(five - seven) < seven)  // = if (2 < 7)
// ...


if (five - seven < -1)          // = if (-2 < -1)
// ...


if (one - six < 1)              // = if (-5 < 1)
// ...


if ((int)(five - seven) < 1)    // = if (-2 < 1)
// ...

but

if (five - seven < 1)   // = if ((unsigned int)-2 < 1) = if (4294967294 < 1)
// ...


if (one - six < five)   // = if ((unsigned int)-5 < 5) = if (4294967291 < 5)
// ...
小开

Well, the first interpretation is correct. However, your reasoning about the "signed semantics" in this context is wrong.

同样，你的第一个解释是正确的。无符号算术遵循模算术的规则，这意味着对于32位无符号类型，0x0000 - 0x0001的计算结果为 0xFFFF。

然而，第二种解释(基于“符号语义”的解释)也需要产生相同的结果。也就是说，即使您在有符号类型的域中计算 0 - 1并获得 -1作为中间结果，这个 -1仍然需要在以后将其转换为无符号类型时生成 0xFFFF。即使某些平台对有符号整数(1的补数、有符号大小)使用了一种特殊的表示形式，在将有符号整数值转换为无符号整数值时，该平台仍然需要应用模算术规则。

例如，这个评估

signed int a = 0, b = 1;
unsigned int c = a - b;

仍然保证在 c中生成 UINT_MAX，即使平台对有符号整数使用奇异的表示。

小开

对于类型为 unsigned int或更大的无符号数，在没有类型转换的情况下，a-b被定义为产生无符号数，当这个无符号数加到 b时，将产生 a。负数到无符号数的转换被定义为产生的数字，当加到符号反转的原始数字时，将产生零(因此将 -5转换为无符号数将产生一个值，当加到5时，将产生零)。

注意，小于 unsigned int的无符号数可能在减法之前被提升为 int类型，a-b的行为将取决于 int的大小。

小开

无符号整数减法已经定义了行为，这也是一个棘手的问题。当减去两个无符号整数时，如果没有显式指定 result (lvalue)类型，result 将升级为更高的 int 类型。例如，在后一种情况下，int8 _ t result = a-b; (其中 a 和 b 具有 int8 _ t 类型)可以获得非常奇怪的行为。我的意思是你可能会失去 transitivity property(也就是说，如果 a > b 和 b > c，那么 a > c 就是真的)。 传递性的丧失会破坏 树型数据结构树型数据结构工作。必须注意不要提供用于排序、搜索以及用无符号整数减法来推断哪个键更高或更低的树生成的比较函数。

请看下面的例子。

#include <stdint.h>
#include <stdio.h>


void main()
{
uint8_t a = 255;
uint8_t b = 100;
uint8_t c = 150;


printf("uint8_t a = %+d, b = %+d, c = %+d\n\n", a, b, c);


printf("          b - a  = %+d\tpromotion to int type\n"
" (int8_t)(b - a) = %+d\n\n"
"          b + a  = %+d\tpromotion to int type\n"
"(uint8_t)(b + a) = %+d\tmodular arithmetic\n"
"     b + a %% %d = %+d\n\n",
b - a,  (int8_t)(b - a),
b + a, (uint8_t)(b + a),
UINT8_MAX + 1,
(b + a) % (UINT8_MAX + 1));


printf("c %s b (b - c = %d), b %s a (b - a = %d), AND c %s a (c - a = %d)\n",
(int8_t)(c - b) < 0 ? "<" : ">", (int8_t)(c - b),
(int8_t)(b - a) < 0 ? "<" : ">", (int8_t)(b - a),
(int8_t)(c - a) < 0 ? "<" : ">", (int8_t)(c - a));
}

$ ./a.out
uint8_t a = +255, b = +100, c = +150


b - a  = -155 promotion to int type
(int8_t)(b - a) = +101


b + a  = +355 promotion to int type
(uint8_t)(b + a) = +99  modular arithmetic
b + a % 256 = +99


c > b (b - c = 50), b > a (b - a = 101), AND c < a (c - a = -105)
小开 
int d = abs(five - seven);  // d =  2

std::abs is not "suitable" for unsigned integers. A cast is needed though.


提交答案