C++的ub还真是无处不在啊

Posted on 2017-11-13 Edited on 2023-10-29 In C++

如何交换两个整型变量?最简单的就是引入第三个变量,然后完成三次赋值达到交换的目的。
然后，也有一些不使用第三个变量达到这个目的的方法。我所知道的有两个，一个是通过位运算的异或（原理是对于任意位模式ｘ^x = 0,在此不展开），还有一个就是通过以下的方法：

template<typename T, typename = typename std::enable_if<std::is_integral<T>::value>::type>
void swap_ingeter(T& x, T& y)
{
	x = x+y;
	y = x-y;
	x = x-y;
}

肯定有人一眼就看出了这个方法的问题：x+y有可能会溢出。

一般程序猿看到溢出就头疼，感觉肯定潜藏着bug，然而事实真是如此吗？这正是本篇文章的想要探讨的问题：这种方法最终结果还能保证交换结果正确吗？

大家都知道，在计算机的世界中，一切的整型最后都是用二进制来表示。对于有符号整型和无符号整型来说，有着不同的编码规则。现在几乎所有的机器都是用补码(two’s complement)来表示有符号数。

所以，对于一个n位的二进制，当它表示一个无符号整型的时候，第i(i取1~~n)位的权重就是2^(i-1)。当它表示一个有符号整型的时候，第n位的权重是-2^(n-1)，第i(i取1~~k-1)位的权重是2^(i-1)。

至于用补码来表示有符号数的一个重要的原因，就是可以在cpu的ALU计算时不用区分有符号和无符号整型，用同一套加法器就能解决。弄不明白为什么也没关系，只要记住结论：有符号整型和无符号整型在cpu上的运算规律相同，即二进制数逐位相加（如果是减法，如A - B，则转换成A + B的补码），最高位进位舍弃。

所以，这些运算最后都能看成是两个无符号二进制数的加法。每次结果对2^k取模。最高位进位被舍弃，既截断。

这在数学上有定义，模数加法形成了一个阿贝尔群。阿贝尔群的性质就是可交换和可结合。看到可交换和可结合，相信大家心里已经有点数了：用上面那个方法交换变量理论上应该是可行的。

我把交换的过程运算详细列出来。

x	y
x+y	y
x+y	x+y-y
x+y-x-y+y	x+y-y

可以看到根据取模加法可交换可结合的特点x最后的结果是x+y-x-y+y=y，y最后的结果x+y-y=x。

到这里似乎完事大吉,但是心头隐隐有些不安。而且某次在某个群里讨论这个话题的时候也被dalao喷过：-（所以感觉这个还和语言的标准有关。后来查了下c++对于有符号数无符号数，以及溢出的资料，果然如此…

对于无符号整型来说：

C++11,§6.9.1

Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2^n where n is the number of bits in the value representation of that particular size of integer

标准是明确规定无符号整型运算结果会以2^n取模，即使溢出了运算结果也是明确数学定义的（mathematically defined）。也就构成了模数加法，可交换可结合。

而对于有符号整型，C++甚至至今(截止到C++17)都没有明确规定过用补码来表示有符号整型，可选的还有one's complement或者sign-and-magnitude。不过C++11倒是在cstdint头文件里规定了几个用补码表示的类型。

C++11, §21.4.1:

The header defines all types and macros the same as the C standard library header <stdint.h>.
See also: ISO C 7.20.

好吧，一切按照c的来：

C11, §7.20.1.1:

The typedef name intN_t designates a signed integer type with width N, no padding bits, and a two’s complement representation. Thus, int8_t denotes such a signed integer type with a width of exactly 8 bits.

可以看到，C++11在cstdint头文件中沿用了C11对于stdint.h的规定，形如intN_t的类型用补码表示。那么对于intN_t类型来说，用文章开头所说的方法能保证一定交换成功吗？

很遗憾，答案仍然是否。因为标准没有明确规定像无符号整型那样，溢出之后对结果取模。也就是说，有符号类型溢出仍然是undefined behavior。所以方法交换的结果也是未定义。

最后的结论：在C++中，无符号整型用上述方法可以交换变量，而有符号整型交换后结果未定义。

ps：不过现在大部分PC机都是x86体系结构的，有符号整型这么交换也是可以的…毕竟cpu运算结果就是那样 orz