Nem*_*emo 83 c++ integer casting integer-overflow language-lawyer
我想定义一个带有unsigned intas参数的函数,并向参数返回一个int全等模UINT_MAX + 1.
第一次尝试可能如下所示:
int unsigned_to_signed(unsigned n)
{
return static_cast<int>(n);
}
但正如任何语言律师所知,从无符号转换为大于INT_MAX的已签名值是实现定义的.
我想实现这一点,以便(a)它只依赖于规范规定的行为; (b)它在任何现代机器上编译成无操作并优化编译器.
对于奇怪的机器......如果没有签名的int congruent将UINT_MAX + 1模数为unsigned 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年的一些假设系统中,它可以做谁知道什么.所以我想说我想避免这种情况.
问题:我的"第三次尝试"应该是什么样的？
回顾一下,我想:
[更新]
让我举一个例子来说明为什么这不是一个微不足道的问题.
考虑具有以下属性的假设C++实现:
sizeof(int) 等于4sizeof(unsigned) 等于4INT_MAX 等于32767INT_MIN等于-2 32 + 32768UINT_MAX等于2 32 - 1int是模2 32(进入范围INT_MIN通过INT_MAX)std::numeric_limits<int>::is_modulo 是真的n为int会保留0 <= n <= 32767的值,否则将产生零在这个假设的实现中,int每个unsigned值只有一个值一致(mod UINT_MAX + 1).所以我的问题很明确.
我声称这个假设的C++实现完全符合C++ 98,C++ 03和C++ 11规范.我承认我没有记住他们所有人的每一句话......但我相信我已仔细阅读了相关章节.因此,如果您希望我接受您的答案,您必须(a)引用一个排除此假设实现的规范或(b)正确处理它.
实际上,正确答案必须处理标准允许的每个假设实施.根据定义,这就是"仅调用标准强制行为"的含义.
顺便提一下,请注意,std::numeric_limits<int>::is_modulo由于多种原因,这里完全没用.首先,true即使未签名到签名的强制转换对大的无符号值不起作用也是如此.另一方面,true如果算术只是模数整个整数范围,它甚至可以在一个补码或符号幅度系统上.等等.如果你的答案取决于is_modulo,那就错了.
[更新2]
HVD的答案教给我的东西:对于整数我假设C++实现不通过现代C.的C99和C11标准允许有非常具体符号整数的表示; 实际上,它们只允许二进制补码,补码和符号幅度(第6.2.6.2节(2);).
但是C++不是C.事实证明,这个事实就在于我的问题的核心.
最初的C++ 98标准是基于更老的C89,它说(第3.1.2.5节):
对于每个有符号整数类型,存在相应的(但不同的)无符号整数类型(使用关键字unsigned指定),它使用相同数量的存储(包括符号信息)并具有相同的对齐要求.有符号整数类型的非负值范围是相应无符号整数类型的子范围,并且每种类型中相同值的表示相同.
C89没有说只有一个符号位或只允许二进制补码/补码/符号幅度.
C++ 98标准几乎逐字采用了这种语言(第3.9.1节(3)):
对于每个有符号整数类型,存在相应的(但不同的)无符号整数类型:"
unsigned char","unsigned short int","unsigned int"和"unsigned long int",每个类型占用相同的存储量并具有相同的对齐要求(3.9 )作为对应的有符号整数类型; 也就是说,每个有符号整数类型具有与其对应的无符号整数类型相同的对象表示.有符号整数类型的非负值范围是相应无符号整数类型的子范围,每个对应的有符号/无符号类型的值表示应相同.
C++ 03标准使用与C++ 11基本相同的语言.
据我所知,没有标准C++规范将其有符号整数表示约束到任何C规范.并且没有强制要求单个标志位或类似的任何东西.它所说的是非负有符号整数必须是相应的无符号整数的子范围.
所以,我再次声称INT_MAX = 32767,允许INT_MIN = -2 32 +32768.如果您的答案另有说明,那么除非您引用证明我错误的C++标准,否则它是不正确的.
小智 67
扩展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,这将不会有任何溢出.
如果这不明显,请查看声明"If x >= -4u,then 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_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描述了标题
<climits>....
内容与标准C库头相同
<limits.h>.
这里,"标准C"表示C99,其规范严格限制了有符号整数的表示.它们就像无符号整数,但有一位专用于"符号",零位或多位专用于"填充".填充位对整数的值没有贡献,并且符号位仅作为二进制补码,一补码或符号幅度.
由于C++ 11继承了<climits>C99中的宏,因此INT_MIN是-INT_MAX或-INT_MAX-1,并且hvd的代码保证可以正常工作.(注意,由于填充,INT_MAX可能比UINT_MAX/2小得多......但是由于signed-> unsigned casts的工作方式,这个答案处理得很好.)
C++ 03/C++ 98比较棘手.它使用相同的措辞继承<climits>"标准C",但现在"标准C"意味着C89/C90.
所有这些 - C++ 98,C++ 03,C89/C90 - 都有我在问题中给出的措辞,但也包括这个(C++ 03第3.9.1节第7段):
积分类型的表示应使用纯二进制计算系统定义值.(44)[ 示例:本国际标准允许2的补码,1的补码和积分类型的带符号幅度表示.
脚注(44)定义了"纯二进制数字系统":
使用二进制数字0和1的整数的位置表示,其中由连续位表示的值是加性的,以1开始,并且乘以2的连续积分幂,除了可能对于具有最高位置的位.
这个措辞的有趣之处在于它与自身相矛盾,因为"纯二进制数字系统"的定义不允许符号/幅度表示!它确实允许高位具有值-2 n-1(二进制补码)或 - (2 n-1 -1)(补码).但是高位导致符号/幅度没有价值.
无论如何,我的"假设实现"在此定义下不符合"纯二进制"的条件,因此它被排除在外.
然而,高位是特殊的这一事实意味着我们可以想象它会贡献任何价值:小的正值,巨大的正值,小的负值或巨大的负值.(如果符号位可以贡献 - (2 n-1 -1),为什么不 - (2 n-1 -2)？等)
所以,让我们想象一个带符号的整数表示,它为"符号"位分配一个古怪的值.
符号位的小正值将导致int(可能大到unsigned)的正范围,并且hvd的代码处理就好了.
符号位的巨大正值将导致int最大值大于unsigned,这是被禁止的.
符号位的巨大负值将导致int表示不连续的值范围,并且规范中的其他措辞将表示出来.
最后,一个符号位如何贡献一个小的负数？我们可以在"符号位"中给1做一个贡献,比如-37到int的值吗？那么INT_MAX将是(例如)2 31 -1而INT_MIN将是-37？
这将导致一些数字具有两个表示......但是一个补码给出两个表示为零,并且根据"示例"允许这样做.规范中没有任何地方说零是唯一可能有两个表示的整数.所以我认为规范允许这个新的假设.
实际上,从-1下降到任何负值-INT_MAX-1似乎都是允许作为"符号位"的值,但不能更小(以免该范围是非连续的).换句话说,INT_MIN可能是从-INT_MAX-1-1到-1.
现在,猜猜怎么着？对于hvd代码中的第二个转换来避免实现定义的行为,我们只需要x - (unsigned)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中有符号的整数有一些严重欠指定的行为,这些行为是由C++ 98/C++ 03继承的.它在C99中修复,C++ 11通过引入<limits.h>C99 间接继承了修复.但即便是C++ 11仍保留了自相矛盾的"纯二进制表示"措辞......
Evg*_*uev 17
此代码仅依赖于规范强制要求的行为,因此很容易满足要求(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)的无操作.英特尔12.1.0拒绝对此进行优化.我没有关于Visual C的信息.
原始答案仅解决了unsigned=>的问题int。如果我们想将“某些无符号类型”的一般问题解决为其对应的有符号类型怎么办？此外，原始答案在引用标准的部分和分析一些极端情况方面非常出色，但它并没有真正帮助我了解它的工作原理，因此该答案将尝试提供强大的概念基础。这个答案将尝试帮助解释“为什么”，并使用现代 C++ 特性来尝试简化代码。
P0907大大简化了这个问题：有符号整数是二进制补码，最终的措辞 P1236被投票纳入 C++20 标准。现在，答案尽可能简单：
template<std::unsigned_integral T>
constexpr auto cast_to_signed_integer(T const value) {
return static_cast<std::make_signed_t<T>>(value);
}
就是这样。A static_cast（或 C 风格的强制转换）最终保证可以完成这个问题所需的事情，而且许多程序员认为它一直在做的事情。
在 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)而不是2^position。这意味着对于所有n - 1位，它们代表相同的值。然后，无符号整数多了一个正常位，这使值的总数加倍（换句话说，设置了该位的值与未设置它的值一样多）。相同的逻辑适用于有符号整数，除了具有该位设置的所有值都是负数。
其他两个合法的整数表示形式，1 的补码和符号大小，除了一个：最负的值外，所有的值都与 2 的补码整数相同。C++根据可表示值的范围，而不是根据位表示，定义了关于整数类型的所有内容，除了reinterpret_cast（和 C++20 std::bit_cast）。这意味着只要我们不尝试创建陷阱表示，我们的分析将适用于这三种表示中的每一种。映射到这个缺失值的无符号值是一个相当不幸的值：位于无符号值中间的那个。幸运的是，我们的第一个条件（在编译时）检查这样的表示是否存在，然后通过运行时检查专门处理它。
第一个条件处理我们在=部分中的情况，这意味着我们处于重叠区域，其中一个值可以在另一个中表示而无需更改。shift_by_window代码中的函数将所有值向下移动每个这些段的大小（我们必须减去最大值然后减去 1 以避免算术溢出问题）。如果我们在该区域之外（我们在该区+域内），我们需要向下跳一个窗口大小。这使我们处于重叠范围内，这意味着我们可以安全地从无符号转换为有符号，因为值没有变化。然而，我们还没有完成，因为我们已经将两个无符号值映射到每个有符号值。因此，我们需要向下移动到下一个窗口（- 区域），以便我们再次拥有唯一的映射。
现在，这是否UINT_MAX + 1按照问题的要求为我们提供了结果一致的 mod ？UINT_MAX + 1等价于2^n，其中n是值表示中的位数。我们用于窗口大小的值等于2^(n - 1)（值序列中的最终索引比大小小 1）。我们减去该值两次，这意味着我们减去2 * 2^(n - 1)等于2^n。加法和减法x在算术 mod 中是无操作的x，所以我们没有影响原始值 mod 2^n。
因为这是一个通用函数而不仅仅是intand unsigned，我们还必须关注积分提升规则。有两种可能有趣的情况：一种short是小于int，另一种short是与 相同的大小int。
short小于int如果short小于int（在现代平台上很常见），那么我们也知道它unsigned short可以放入 an 中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;
}
}
在这里，我们看到，铛，GCC和ICC不产生代码cast，并cast_to_signed_integer_basic在-O2和-O3，和MSVC产生的任何代码/O2，因此该解决方案是最优的。