c++ - 有效的无符号到有符号转换避免实现定义的行为

Question

我想定义一个接受 unsigned int 的函数作为参数并返回 int全等模 UINT_MAX+1 到参数。

第一次尝试可能如下所示:

int unsigned_to_signed(unsigned n)
{
    return static_cast<int>(n);
}

但是任何语言律师都知道，对于大于 INT_MAX 的值，从无符号转换为有符号是实现定义的。

我想实现这一点，以便(a)它只依赖于规范规定的行为； (b) 它在任何现代机器和优化编译器上编译为无操作。

至于奇怪的机器......如果没有签名的int全等模UINT_MAX+1到无符号的int，假设我想抛出一个异常。如果有多个(我不确定这是否可能)，假设我想要最大的一个。

好的，第二次尝试:

int unsigned_to_signed(unsigned n)
{
    int int_n = static_cast<int>(n);

    if (n == static_cast<unsigned>(int_n))
        return int_n;

    // else do something long and complicated
}

当我不在典型的二进制补码系统上时，我不太关心效率，因为在我看来，这不太可能。如果我的代码成为 2050 年无所不在的符号幅度系统的瓶颈，那么，我敢打赌有人可以解决这个问题并对其进行优化。

现在，第二次尝试非常接近我想要的。虽然投到 int对于某些输入是实现定义的，转换回 unsigned标准保证保留模 UINT_MAX+1 的值。因此，条件确实会检查我想要的内容，并且在我可能遇到的任何系统上它都不会编译为任何内容。

但是......我仍然转换到 int无需首先检查它是否会调用实现定义的行为。在 2050 年的某个假设系统中，它可以做谁知道呢。所以假设我想避免这种情况。

问题:我的“第三次尝试”应该是什么样的？

回顾一下，我想:

从无符号整数转换为有符号整数

保留值 mod UINT_MAX+1

仅调用标准规定的行为

使用优化编译器在典型的二进制补码机器上编译为无操作

[更新]

让我举一个例子来说明为什么这不是一个微不足道的问题。

考虑具有以下属性的假设 C++ 实现:

sizeof(int)等于 4

sizeof(unsigned)等于 4

INT_MAX等于 32767

INT_MIN等于 -232 + 32768

UINT_MAX等于 232 - 1

算术上 int是模 232(在 INT_MIN 到 INT_MAX 范围内)

std::numeric_limits<int>::is_modulo是真的

类型转换未签名 n to int 保留 0 <= n <= 32767 的值，否则产生零

在这个假设的实现中，正好有一个 int值一致 (mod UINT_MAX+1) 到每个 unsigned值(value)。所以我的问题将是明确的。

我声称这个假设的 C++ 实现完全符合 C++98、C++03 和 C++11 规范。我承认我没有记住所有的单词……但我相信我已经仔细阅读了相关部分。因此，如果您希望我接受您的答案，您要么必须 (a) 引用排除此假设实现的规范，要么 (b) 正确处理它。

事实上，正确的答案必须处理标准允许的每个假设实现。根据定义，这就是“仅调用标准规定的行为”的含义。

顺便提一下， std::numeric_limits<int>::is_modulo由于多种原因，这里完全没用。一方面，它可以是 true即使 unsigned-to-signed 转换不适用于大的无符号值。另一个，可以是 true即使在补码或符号大小系统上，如果算术只是对整个整数范围取模。等等。如果您的答案取决于 is_modulo ，错了。

[更新2]

hvd's answer教会了我一些东西:现代 C 不允许我对整数的假设 C++ 实现。C99 和 C11 标准对有符号整数的表示非常具体；实际上，它们只允许二进制补码、一个补码和符号大小(第 6.2.6.2 节第 (2); 节)。

但 C++ 不是 C。事实证明，这个事实是我问题的核心。

最初的 C++98 标准基于更老的 C89，它说(第 3.1.2.5 节):

For each of the signed integer types, there is a corresponding (but different) unsigned integer type (designated with the keyword unsigned) that uses the same amount of storage (including sign information) and has the same alignment requirements. The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type, and the representation of the same value in each type is the same.

C89 没有说明只有一个符号位或只允许二进制补码/一个补码/符号大小。

C++98 标准几乎逐字采用了这种语言(第 3.9.1 节第 (3) 段):

For each of the signed integer types, there exists a corresponding (but different) unsigned integer type: "unsigned char", "unsigned
short int", "unsigned int", and "unsigned long int", each of which occupies the same amount of storage and has the same alignment requirements (3.9) as the corresponding signed integer type ; that is, each signed integer type has the same object representation as its corresponding unsigned integer type. The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type, and the value representation of each corresponding signed/unsigned type shall be the same.

C++03 标准使用基本相同的语言，C++11 也是如此。

据我所知，没有标准的 C++ 规范将其有符号整数表示限制为任何 C 规范。并且没有强制要求单个符号位或任何类型的东西。它只是说非负有符号整数必须是相应无符号整数的子范围。

所以，我再次声明 INT_MAX=32767 和 INT_MIN=-232+32768 是允许的。如果您的答案另有假设，则除非您引用 ，否则这是不正确的。 C++ 标准证明我错了。

Answer 1

扩展 user71404 的回答:

int f(unsigned x)
{
    if (x <= INT_MAX)
        return static_cast<int>(x);

    if (x >= INT_MIN)
        return static_cast<int>(x - INT_MIN) + INT_MIN;

    throw x; // Or whatever else you like
}

如 x >= INT_MIN (记住促销规则， INT_MIN 被转换为 unsigned )，然后 x - INT_MIN <= INT_MAX ，所以这不会有任何溢出。

如果这不明显，请查看声明“如果 x >= -4u ，则 x + 4 <= 3 。”，并记住 INT_MAX将至少等于 -INT_MIN - 1 的数学值。

在最常见的系统上，其中 !(x <= INT_MAX)暗示 x >= INT_MIN ，优化器应该能够(并且在我的系统上，能够)删除第二个检查，确定两个 return语句可以编译为相同的代码，也可以删除第一个检查。生成的程序集列表:

__Z1fj:
LFB6:
    .cfi_startproc
    movl    4(%esp), %eax
    ret
    .cfi_endproc

您问题中的假设实现:

INT_MAX 等于 32767

INT_MIN 等于 -232 + 32768

是不可能的，所以不需要特别考虑。 INT_MIN将等于 -INT_MAX ，或至 -INT_MAX - 1 .这遵循 C 对整数类型的表示 (6.2.6.2)，它需要 n位是值位，一位是符号位，并且只允许一种单一的陷阱表示(不包括由于填充位而无效的表示)，即表示负零的表示/ -INT_MAX - 1 . C++ 不允许任何超出 C 允许的整数表示。

更新 : 微软的编译器显然没有注意到 x > 10和 x >= 11测试同样的事情。如果 x >= INT_MIN，它只生成所需的代码替换为 x > INT_MIN - 1u ，它可以检测为 x <= INT_MAX 的否定(在这个平台上)。

[来自提问者 (Nemo) 的更新，详细说明我们在下面的讨论]

我现在相信这个答案适用于所有情况，但原因很复杂。我可能会为此解决方案提供赏金，但我想捕捉所有血腥细节，以防有人关心。

让我们从 C++11 的 18.3.3 节开始:

Table 31 describes the header <climits>.

...

The contents are the same as the Standard C library header <limits.h>.

此处，“标准 C”表示 C99，其规范严格限制了有符号整数的表示。它们就像无符号整数，但有一位专用于“符号”，而零位或多位专用于“填充”。填充位不影响整数值，符号位仅作为二进制补码、一补码或符号大小起作用。

由于 C++11 继承了 <climits>来自 C99 的宏，INT_MIN 是 -INT_MAX 或 -INT_MAX-1，并且 hvd 的代码保证可以工作。 (请注意，由于填充，INT_MAX 可能比 UINT_MAX/2 小得多......但由于有符号-> 无符号强制转换的工作方式，这个答案处理得很好。)

C++03/C++98 比较棘手。它使用相同的措辞来继承 <climits>来自“标准C”，但现在“标准C”意味着C89/C90。

所有这些——C++98、C++03、C89/C90——都有我在我的问题中给出的措辞，但也包括这个(C++03 第 3.9.1 节第 7 段):

The representations of integral types shall define values by use of a pure binary numeration system.(44) [Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types.]

脚注 (44) 定义了“纯二进制数字系统”:

A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps for the bit with the highest position.

这个措辞的有趣之处在于它自相矛盾，因为“纯二进制计数系统”的定义不允许符号/大小表示!它确实允许高位具有值 -2n-1(二进制补码)或 -(2n-1-1)(一个补码)。但是导致符号/幅度的高位没有值。

无论如何，我的“假设实现”在此定义下不符合“纯二进制”的条件，因此排除在外。

然而，高位是特殊的这一事实意味着我们可以想象它贡献了任何值(value):一个小的正值、巨大的正值、小的负值或巨大的负值。 (如果符号位可以贡献 -(2n-1-1)，为什么不 -(2n-1-2)？等)

所以，让我们想象一个有符号整数表示，它为“符号”位分配一个古怪的值。

符号位的小正值将导致 int 的正范围(可能和 unsigned 一样大)，并且 hvd 的代码处理得很好。

符号位的巨大正值将导致 int最大值大于 unsigned ，这是被禁止的。

符号位的巨大负值将导致 int表示非连续范围的值，规范中的其他措辞排除了这一点。

最后，贡献一个小的负数的符号位怎么样？我们是否可以在“符号位”中有一个 1 对 int 的值有贡献，比如说 -37？那么 INT_MAX 将是(比如说)231-1 而 INT_MIN 将是 -37？

这将导致某些数字具有两种表示形式......但是ones-complement 将两种表示形式归零，根据“示例”，这是允许的。规范中没有任何地方说零是唯一可能有两种表示形式的整数。所以我认为这个新的假设是规范允许的。

实际上，从 -1 到 -INT_MAX-1 的任何负值似乎允许作为“符号位”的值，但不能更小(以免范围不连续)。换句话说， INT_MIN可能来自 -INT_MAX-1到-1。

现在，你猜怎么着？对于 hvd 代码中的第二个强制转换以避免实现定义的行为，我们只需要 x - (unsigned)INT_MIN小于或等于 INT_MAX .我们刚刚展示了 INT_MIN至少是 -INT_MAX-1 .显然， x最多是 UINT_MAX .将负数转换为无符号数与添加 UINT_MAX+1 相同.把它们放在一起:

x - (unsigned)INT_MIN <= INT_MAX

当且仅当

UINT_MAX - (INT_MIN + UINT_MAX + 1) <= INT_MAX
-INT_MIN-1 <= INT_MAX
-INT_MIN <= INT_MAX+1
INT_MIN >= -INT_MAX-1

最后一个是我们刚刚展示的，所以即使在这种反常的情况下，代码实际上也能工作。

这用尽了所有的可能性，从而结束了这个极其学术的练习。

底线:C89/C90 中的有符号整数有一些严重未指定的行为，这些行为被 C++98/C++03 继承。它在 C99 中被修复，C++11 通过合并 <limits.h> 间接继承了修复。来自 C99。但即使是 C++11 也保留了自相矛盾的“纯二进制表示”措辞……