高效的无符号到有符号转换避免了实现定义的行为

Question

我想定义一个函数，该函数将无符号int作为参数，并将int全等模UINT_MAX1返回给参数。

第一次尝试可能是这样的：

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

但正如任何语言律师所知道的那样，为大于INT_MAX的值从无符号转换为签名是实现定义的。

我想实现它，以便（a）它只依赖于规范规定的行为；（b）它在任何现代机器上编译成无操作并优化编译器。

至于奇怪的机器。。。如果没有与无符号int相合的模UINT_MAX 1，假设我想抛出一个异常。如果不止一个（我不确定这是否可行），就说我想要最大的一个。

好的，第二次尝试：

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的转换是为某些输入定义的实现，但标准保证对无符号的转换保留模UINT_MAX 1的值。因此，条件确实检查了我想要的东西，并且在我可能遇到的任何系统上，它都不会编译成任何东西。

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

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

总而言之，我想：

• 从无符号int强制转换为有符号int
• 保留值modUINT_MAX1
• 仅调用标准强制行为
• 使用优化编译器在典型的双补码机器上编译成无操作

[更新]

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

假设C实现具有以下属性：

• sizeof（int）等于4
• sizeof（无符号）等于4
• INT_MAX等于32767
• INT_MINequals-2³²32768
• UINT_MAX等于2³²-1
• int上的算术是模2³²（在int_MIN到int_MAX的范围内）
• std:：数值限制

在这个假设的实现中，每个无符号的值正好有一个int值全等（mod UINT_MAX 1）。所以我的问题会很明确。

我声称这个假设的C实现完全符合C98、C03和C11规范。我承认我没有记住所有的单词。。。但我相信我已经仔细阅读了相关章节。所以，如果你想让我接受你的答案，你要么（a）引用一个规范，排除这个假设的实现，要么（b）正确处理它。

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

顺便说一句，请注意std:：numeric_limits

[更新2]

HVD的回答教会了我一些东西：我对整数的假设C实现是现代C不允许的。C99和C11标准对有符号整数的表示非常具体；事实上，它们只允许twos-补码、one-补码和符号-幅度（第6.2.6.2节第（2）段；）。

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

最初的C98标准是基于旧得多的C89，它说（第3.1.2.5节）：

对于每个有符号整数类型，都有一个对应的（但不同的）无符号整数类型（用关键字unsigned指定），该类型使用相同的存储量（包括符号信息），并且具有相同的对齐要求。有符号整数类型的非负值范围是相应无符号整数类型的子范围，并且每种类型中相同值的表示形式相同。

C89没有提到只有一个符号位或只允许两个补码/一个补码/符号大小。

C 98标准几乎一字不差地采用了这种语言（第3.9.1节第（3）段）：

对于每种有符号整数类型，都存在一个对应的（但不同的）无符号整数类型：“无符号字符”、“无符号短整型”、“无符号整型”和“无符号长整型”，每种类型占用的存储量和与相应的有符号整数类型相同的对齐要求（3.9）；也就是说，每个有符号整数类型与其对应的无符号整数类型具有相同的对象表示形式。有符号整数类型的非负值范围是相应无符号整数类型的子范围，每个相应有符号/无符号类型的值表示应相同。

C 03标准和C 11使用基本相同的语言。

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

所以，我再次声明允许INT_MAX=32767，INT_MIN=-23232768。如果你的答案是否定的，除非你引用C标准来证明我错了。




Answer 1

匿名用户

原来的答案只解决了未签名的问题=

P0907大大简化了这个问题：有符号整数是2的补码，是投票进入C 20标准的最终措辞P1236。现在，答案尽可能简单：

template<std::unsigned_integral T>
constexpr auto cast_to_signed_integer(T const value) {
    return static_cast<std::make_signed_t<T>>(value);
}

就是这样。一个static_cast（或C风格的强制转换）最终可以保证做你需要做的这个问题的事情，以及许多程序员认为它总是做的事情。

在C17中，情况要复杂得多。我们必须处理三种可能的整数表示（2的补码、1的补码和符号大小）。即使在我们知道它必须是2的补码的情况下，因为我们检查了可能值的范围，将带符号整数范围之外的值转换为该带符号整数仍然会得到实现定义的结果。我们必须像在其他答案中看到的那样使用技巧。

首先，这是如何一般解决问题的代码：

template<typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
constexpr auto cast_to_signed_integer(T const value) {
    using result = std::make_signed_t<T>;
    using result_limits = std::numeric_limits<result>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<T>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<result>(value);
    } else {
        using promoted_unsigned = std::conditional_t<sizeof(T) <= sizeof(unsigned), unsigned, T>;
        using promoted_signed = std::make_signed_t<promoted_unsigned>;
        constexpr auto shift_by_window = [](auto x) {
            // static_cast to avoid conversion warning
            return x - static_cast<decltype(x)>(result_limits::max()) - 1;
        };
        return static_cast<result>(
            shift_by_window( // shift values from common range to negative range
                static_cast<promoted_signed>(
                    shift_by_window( // shift large values into common range
                        static_cast<promoted_unsigned>(value) // cast to avoid promotion to int
                    )
                )
            )
        );
    }
}

这比公认的答案有更多的强制转换，这是为了确保编译器没有出现有符号/无符号不匹配警告，并正确处理整数提升规则。

我们首先对不是二补码的系统有一个特殊情况（因此我们必须专门处理最大可能值，因为它没有任何东西可以映射到）。之后，我们进入真正的算法。

第二个顶级条件很简单：我们知道该值小于或等于最大值，因此它适合结果类型。即使有注释，第三个条件也有点复杂，因此一些示例可能有助于理解为什么每个语句都是必要的。

首先，这个窗口概念是什么？考虑以下数字行：

   |   signed   |
<.........................>
          |  unsigned  |

事实证明，对于2的补码整数，你可以将任意一种类型可以到达的数字行的子集分成三个大小相等的类别：

- => signed only
= => both
+ => unsigned only

<..-------=======+++++++..>

这可以很容易地通过考虑代表性来证明。无符号整数从0开始，使用所有位以2的幂增加值。有符号整数对于除符号位之外的所有位都是完全相同的，符号位的值是-（2^位置），而不是2^位置。这意味着对于所有n-1位，它们代表相同的值。然后，无符号整数又有一个正常位，使值的总数加倍（换句话说，设置该位的值与未设置该位的值一样多）。有符号整数的逻辑相同，只是该位集的所有值都是负数。

另外两种法定整数表示法“一”的补码和符号大小与“二”的补码整数具有相同的值，除了一个：最负的值。C根据可表示值的范围而不是位表示来定义整数类型的所有内容，除了重新解释（和C 20std:：bit _cast）。这意味着，只要我们不尝试创建陷阱表示，我们的分析将适用于这三种表示。映射到此缺失值的无符号值是一个非常不幸的值：位于无符号值中间的值。幸运的是，我们的第一个条件检查（在编译时）是否存在这样的表示，然后通过运行时检查专门处理它。

第一个条件处理的是=部分中的情况，这意味着我们处于重叠区域，其中一个区域中的值可以在另一个区域中表示，而不会发生变化。代码中的shift_by_窗口函数将所有值按每个段的大小向下移动（我们必须先减去最大值，然后再减去1，以避免算术溢出问题）。如果我们在该区域之外（我们在区域），我们需要跳转一个窗口大小。这将我们置于重叠范围内，这意味着我们可以安全地从无符号转换为有符号，因为值没有变化。然而，我们还没有完成，因为我们已经将两个无符号值映射到每个有符号值。因此，我们需要向下切换到下一个窗口（-区域），以便再次获得唯一的映射。

现在，这是否为我们提供了一个结果全等modUINT_MAX1，正如问题中要求的那样？UINT_MAX1等价于2^n，其中n是值表示中的位数。我们用于窗口大小的值等于2^（n-1）（值序列中的最终索引比大小少一个）。我们减去该值两次，这意味着我们减去2*2^（n-1），这等于2^n。加减x是算术modx中的禁忌，因此我们没有影响原始值mod2^n。

因为这是一个通用函数，而不仅仅是int和unsigned，我们还必须关注积分提升规则。可能有两种有趣的情况：一种是short小于int，另一种是short与int大小相同。

如果short小于int（在现代平台上很常见），那么我们也知道unsigned short可以放入int，这意味着对它的任何操作实际上都会在int中发生，因此我们显式地强制转换为升级类型以避免这种情况。我们的最终陈述是相当抽象的，如果我们用真实的价值代替它，就更容易理解。对于我们的第一个有趣的例子，在不损失一般性的情况下，让我们考虑一个16位的short和一个17位的int（这在新规则下仍然是允许的，只意味着这两个整数类型中至少有一个有一些填充位）：

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int17_t>(
            shift_by_window(
                static_cast<uint17_t>(value)
            )
        )
    )
);

求解最大可能的16位无符号值

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return int16_t(
    shift_by_window(
        int17_t(
            shift_by_window(
                uint17_t(65535)
            )
        )
    )
);

简化为

return int16_t(
    int17_t(
        uint17_t(65535) - uint17_t(32767) - 1
    ) -
    int17_t(32767) -
    1
);

简化为

return int16_t(
    int17_t(uint17_t(32767)) -
    int17_t(32767) -
    1
);

简化为

return int16_t(
    int17_t(32767) -
    int17_t(32767) -
    1
);

简化为

return int16_t(-1);

我们输入了最大可能的未签名，然后返回-1，成功！

如果short的大小与int的大小相同（在现代平台上不常见），则整体升级规则略有不同。在这种情况下，short升级为int，unsigned short升级为unsigned。幸运的是，我们显式地将每个结果转换为我们希望在其中进行计算的类型，因此最终不会出现问题。在不损失一般性的情况下，让我们考虑一个16位short和一个16位int：

constexpr auto shift_by_window = [](auto x) {
    return x - static_cast<decltype(x)>(32767) - 1;
};
return static_cast<int16_t>(
    shift_by_window(
        static_cast<int16_t>(
            shift_by_window(
                static_cast<uint16_t>(value)
            )
        )
    )
);

求解最大可能的16位无符号值

auto x = int16_t(
    uint16_t(65535) - uint16_t(32767) - 1
);
return int16_t(
    x - int16_t(32767) - 1
);

简化为

return int16_t(
    int16_t(32767) - int16_t(32767) - 1
);

简化为

return int16_t(-1);

我们输入了最大可能的未签名，然后返回-1，成功！

constexpr int cast_to_signed_integer(unsigned const value) {
    using result_limits = std::numeric_limits<int>;
    if constexpr (result_limits::min() + 1 != -result_limits::max()) {
        if (value == static_cast<unsigned>(result_limits::max()) + 1) {
            throw std::runtime_error("Cannot convert the maximum possible unsigned to a signed value on this system");
        }
    }
    if (value <= result_limits::max()) {
        return static_cast<int>(value);
    } else {
        constexpr int window = result_limits::min();
        return static_cast<int>(value + window) + window;
    }
}

https://godbolt.org/z/74hY81

在这里，我们看到，clang、gcc和icc在-O2和-O3处没有为cast和cast_to_signed_integer_basic生成代码，而MSVC在/O2处没有生成代码，因此解决方案是最优的。

Answer 2

该代码仅依赖于规范规定的行为，因此很容易满足要求（a）：

int unsigned_to_signed(unsigned n)
{
  int result = INT_MAX;

  if (n > INT_MAX && n < INT_MIN)
    throw runtime_error("no signed int for this number");

  for (unsigned i = INT_MAX; i != n; --i)
    --result;

  return result;
}

对于需求（b）就不那么容易了。这使用gcc 4.6.3（-Os、-O2、-O3）和clang 3.0（-Os、-O、-O2、-O3）编译成无操作。Intel 12.1.0拒绝优化此功能。我没有关于Visual C的信息。

Answer 3

扩展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

如果这不明显，请看一看“Ifx”的说法

在最常见的系统上，！（十）

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

你问题中的假设实现：

• INT_MAX等于32767
• INT_MIN等于-2³²32768

不可能，因此不需要特别考虑INT_MIN将等于-INT_MAX，或等于-INT_MAX-1。这源于C对整数类型的表示（6.2.6.2），它要求n位为值位，一位为符号位，并且只允许一个陷阱表示（不包括因填充位而无效的表示），即表示负零的表示。C不允许任何超出C允许范围的整数表示。

更新：微软的编译器显然没有注意到x

[发问者（Nemo）的最新消息，详细说明我们下面的讨论]

我现在相信这个答案在所有情况下都有效，但原因很复杂。我可能会奖励这个解决方案，但我想捕捉所有血腥的细节，以防有人在乎。

让我们从C 11开始，第18.3.3节：

表31描述了标题

...

内容与Standard C库头相同

在这里，“标准C”是指C99，其规范严重限制了有符号整数的表示。它们就像无符号整数，但有一位专用于“符号”，零位或多位专用于“填充”。填充位不贡献整数的值，符号位仅贡献为二补码、一补码或符号幅度。

由于C 11继承了

C 03/C 98更为棘手。它使用相同的措辞来继承

所有这些——C 98、C 03、C89/C90——都有我在问题中给出的措辞，但也包括以下内容（C 03第3.9.1节第7段）：

积分类型的表示应使用纯二进制计算系统定义值。（44）[示例：本国际标准允许整数类型的2的补码、1的补码和符号大小表示。]

脚注（44）定义了“纯二进制计数系统”：

使用二进制数字0和1的整数的位置表示，其中由连续位表示的值是加法的，以1开头，并乘以2的连续整数幂，位置最高的位除外。

这句话的有趣之处在于它自相矛盾，因为“纯二进制数制”的定义不允许符号/量级表示！它确实允许高位具有值-2n-1（两个补码）或-（2n-1-1）（一个补码）。但是，导致符号/大小的高位没有值。

无论如何，在这个定义下，我的“假设实现”不符合“纯二进制”的条件，所以它被排除在外。

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

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

符号位的小正值将导致int的正范围（可能与unsign一样大），而hvd的代码处理得很好。

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

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

最后，用一个符号位来表示一个小的负数怎么样？我们能在“符号位”中加一个1，比如说，对int的值加-37吗？那么INT_MAX应该是（比如）231-1，INT_MIN应该是-37？

这将导致一些数字有两个表示...但是一补码给零两个表示，根据“示例”，这是允许的。规范没有说零是唯一可能有两个表示的整数。所以我认为这个新假设是规范允许的。

实际上，从-1到-INT_MAX-1的任何负值似乎都可以作为“符号位”的值，但不能更小（以免范围不连续）。换句话说，INT_MIN可以是-INT_MAX-1到-1之间的任何值。

你猜怎么着？对于hvd代码中的第二个强制转换以避免实现定义的行为，我们只需要x-（无符号）INT_MIN小于或等于INT_MAX。我们刚刚展示了INT_MIN至少是-INT_MAX-1。显然，x最多是UINT_MAX。将负数转换为unsigned与添加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中的有符号整数有一些严重不足的行为，这些行为被C98/C03继承。它在C99中是固定的，C 11通过合并