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

扩展 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 节开始：

表 31 描述了标题 。 ... 内容与标准 C 库头文件 相同。

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

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

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

所有这些——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 的正范围（可能与 unsigned 一样大），并且 hvd 的代码处理得很好。

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

符号位的巨大负值将导致 int 表示不连续的值范围，并且规范中的其他措辞将其排除在外。

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

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

实际上，从 -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 通过合并 C99 中的 <limits.h> 间接继承了该修复。但即使是 C++11 也保留了自相矛盾的“纯二进制表示”措辞……

---

此代码仅依赖于规范规定的行为，因此很容易满足要求 (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 的信息。

---

原始答案仅解决了 unsigned => 的问题。 int。如果我们想将“一些无符号类型”的一般问题解决到其对应的有符号类型怎么办？此外，原始答案在引用标准部分和分析一些极端案例方面非常出色，但它并没有真正帮助我了解它为什么起作用，所以这个答案将试图提供一个强有力的概念基础。这个答案将尝试帮助解释“为什么”，并使用现代 C++ 功能来尝试简化代码。

C++20 答案

使用 P0907: Signed Integers are Two’s Complement 和被选入 C++20 标准的 final wording 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 风格的转换）最终可以保证完成这个问题所需的事情，以及许多程序员认为它一直在做的事情。

C++17 答案

在 C++17 中，事情要复杂得多。我们必须处理三种可能的整数表示（二进制补码、二进制补码和符号幅度）。即使在我们知道它必须是二进制补码的情况下，因为我们检查了可能值的范围，将有符号整数范围之外的值转换为该有符号整数仍然会给我们一个实现定义的结果。我们必须使用我们在其他答案中看到的技巧。

首先，这里是如何解决这个问题的代码：

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
                    )
                )
            )
        );
    }
}

这比接受的答案要多一些，这是为了确保编译器没有带符号/无符号的不匹配警告，并正确处理整数提升规则。

对于不是二进制补码的系统，我们首先有一个特殊情况（因此我们必须特别处理最大可能值，因为它没有任何要映射的内容）。在那之后，我们得到了真正的算法。

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

概念基础：数轴

首先，这个 window 概念是什么？考虑以下数轴：

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

事实证明，对于二进制补码整数，您可以将任一类型可以到达的数轴子集划分为三个大小相等的类别：

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

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

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

其他两种合法的整数表示，一个的补码和符号幅度，除了一个：最负值之外，都具有与二进制补码整数相同的值。 C++ 定义了关于整数类型的所有内容，除了 reinterpret_cast（和 C++20 std::bit_cast）之外，都是根据可表示值的范围，而不是根据位表示。这意味着只要我们不尝试创建陷阱表示，我们的分析将适用于这三种表示中的每一种。映射到这个缺失值的无符号值是一个相当不幸的值：位于无符号值中间的那个。幸运的是，我们的第一个条件检查（在编译时）是否存在这样的表示，然后通过运行时检查对其进行特殊处理。

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

现在，这是否为我们提供了问题中要求的结果全等 mod UINT_MAX + 1？ UINT_MAX + 1 等效于 2^n，其中 n 是值表示中的位数。我们用于窗口大小的值等于 2^(n - 1)（值序列中的最终索引比大小小 1）。我们将该值减去两次，这意味着我们减去等于 2^n 的 2 * 2^(n - 1)。加减 x 是算术 mod x 中的空操作，因此我们没有影响原始值 mod 2^n。

正确处理整数促销

因为这是一个通用函数而不仅仅是 int 和 unsigned，我们还必须关注整体提升规则。有两种可能有趣的情况：一种是 short 小于 int，另一种是 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 大小相同（在现代平台上不常见），则整体提升规则略有不同。在这种情况下，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，成功！

如果我只关心 int 和 unsigned 而不关心警告怎么办，就像原来的问题一样？

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 处没有生成代码，因此解决方案是最优的。

---

你可以明确地告诉编译器你想做什么：

int unsigned_to_signed(unsigned n) {
  if (n > INT_MAX) {
    if (n <= UINT_MAX + INT_MIN) {
      throw "no result";
    }
    return static_cast<int>(n + INT_MIN) - (UINT_MAX + INT_MIN + 1);
  } else {
    return static_cast<int>(n);
  }
}

使用 gcc 4.7.2 编译 x86_64-linux (g++ -O -S test.cpp) 以

_Z18unsigned_to_signedj:
    movl    %edi, %eax
    ret

---

如果 x 是我们的输入...

如果是 x > INT_MAX，我们希望找到一个常数 k，使得 0 < x - k*INT_MAX < INT_MAX。

这很简单——unsigned int k = x / INT_MAX;。然后，让 unsigned int x2 = x - k*INT_MAX;

我们现在可以安全地将 x2 转换为 int。让int x3 = static_cast<int>(x2);

如果 k > 0，我们现在要从 x3 中减去 UINT_MAX - k * INT_MAX + 1。

现在，在 2s 补码系统上，只要 x > INT_MAX，这可以：

unsigned int k = x / INT_MAX;
x -= k*INT_MAX;
int r = int(x);
r += k*INT_MAX;
r -= UINT_MAX+1;

请注意，UINT_MAX+1 在 C++ 中保证为零，转换为 int 是一个 noop，我们减去 k*INT_MAX 然后将其添加回“相同的值”。所以一个可接受的优化器应该能够消除所有这些愚蠢的事情！

这留下了 x > INT_MAX 与否的问题。好吧，我们创建了 2 个分支，一个带有 x > INT_MAX，一个没有。没有的会进行严格转换，编译器会将其优化为 noop。带有 ... 的那个在优化器完成后执行 noop。智能优化器将两个分支实现为同一事物，并删除该分支。

问题：如果 UINT_MAX 相对于 INT_MAX 真的很大，上述方法可能不起作用。我假设 k*INT_MAX <= UINT_MAX+1 隐含。

我们可能会使用一些枚举来攻击它，例如：

enum { divisor = UINT_MAX/INT_MAX, remainder = UINT_MAX-divisor*INT_MAX };

我相信在 2s 补码系统上可以计算出 2 和 1（我们保证该数学可以工作吗？这很棘手......），并基于这些轻松优化非 2s 补码系统的逻辑......

这也打开了异常情况。仅当 UINT_MAX 远大于 (INT_MIN-INT_MAX) 时才有可能，因此您可以将异常代码放在 if 块中以某种方式准确地询问该问题，并且它不会减慢您在传统系统上的速度。

我不确定如何构造那些编译时常量来正确处理它。

---

std::numeric_limits<int>::is_modulo 是编译时间常数。因此您可以将其用于模板专业化。问题解决了，至少如果编译器与内联一起使用。

#include <limits>
#include <stdexcept>
#include <string>

#ifdef TESTING_SF
    bool const testing_sf = true;
#else
    bool const testing_sf = false;
#endif

// C++ "extensions"
namespace cppx {
    using std::runtime_error;
    using std::string;

    inline bool hopefully( bool const c ) { return c; }
    inline bool throw_x( string const& s ) { throw runtime_error( s ); }

}  // namespace cppx

// C++ "portability perversions"
namespace cppp {
    using cppx::hopefully;
    using cppx::throw_x;
    using std::numeric_limits;

    namespace detail {
        template< bool isTwosComplement >
        int signed_from( unsigned const n )
        {
            if( n <= unsigned( numeric_limits<int>::max() ) )
            {
                return static_cast<int>( n );
            }

            unsigned const u_max = unsigned( -1 );
            unsigned const u_half = u_max/2 + 1;

            if( n == u_half )
            {
                throw_x( "signed_from: unsupported value (negative max)" );
            }

            int const i_quarter = static_cast<int>( u_half/2 );
            int const int_n1 = static_cast<int>( n - u_half );
            int const int_n2 = int_n1 - i_quarter;
            int const int_n3 = int_n2 - i_quarter;

            hopefully( n == static_cast<unsigned>( int_n3 ) )
                || throw_x( "signed_from: range error" );

            return int_n3;
        }

        template<>
        inline int signed_from<true>( unsigned const n )
        {
            return static_cast<int>( n );
        }
    }    // namespace detail

    inline int signed_from( unsigned const n )
    {
        bool const is_modulo = numeric_limits< int >::is_modulo;
        return detail::signed_from< is_modulo && !testing_sf >( n );
    }
}    // namespace cppp

#include <iostream>
using namespace std;
int main()
{
    int const x = cppp::signed_from( -42u );
    wcout << x << endl;
}

编辑

n-1

n

整数

---

我认为 int 类型至少是两个字节，所以 INT_MIN 和 INT_MAX 在不同的平台上可能会发生变化。

Fundamental types

≤climits≥ header

---

我的钱花在了使用 memcpy 上。任何体面的编译器都知道优化它：

#include <stdio.h>
#include <memory.h>
#include <limits.h>

static inline int unsigned_to_signed(unsigned n)
{
    int result;
    memcpy( &result, &n, sizeof(result));
    return result;
}

int main(int argc, const char * argv[])
{
    unsigned int x = UINT_MAX - 1;
    int xx = unsigned_to_signed(x);
    return xx;
}

对我来说（Xcode 8.3.2、Apple LLVM 8.1、-O3），这会产生：

_main:                                  ## @main
Lfunc_begin0:
    .loc    1 21 0                  ## /Users/Someone/main.c:21:0
    .cfi_startproc
## BB#0:
    pushq    %rbp
Ltmp0:
    .cfi_def_cfa_offset 16
Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp2:
    .cfi_def_cfa_register %rbp
    ##DEBUG_VALUE: main:argc <- %EDI
    ##DEBUG_VALUE: main:argv <- %RSI
Ltmp3:
    ##DEBUG_VALUE: main:x <- 2147483646
    ##DEBUG_VALUE: main:xx <- 2147483646
    .loc    1 24 5 prologue_end     ## /Users/Someone/main.c:24:5
    movl    $-2, %eax
    popq    %rbp
    retq
Ltmp4:
Lfunc_end0:
    .cfi_endproc

---