现代硬件算法[6.6]: 整数
整数
如果你从一开始就按顺序阅读本章,你可能会想:为什么我要在介绍完浮点数之后才介绍整数运算?整数不是应该更容易吗?
没错:整数表示更简单。但是,与直觉相反的是,这种简单性反而使得可以有更多的操作方式。相比之下,浮点数的表示往往需要硬件的支持,而有效地操作整数则需要更多创新性的指令集使用方式。
二进制格式
无符号整数就是写作二进制的自然数:
当运算的结果超出当前整数类型尺寸所能表示的范围(如,对32位无符号整型而言,大于或等于),就会溢出(overflow),只留下结果的低32位。同样的,如果结果是一个负值,32位无符号整数无法直接表示负数。这种情况就叫作下溢(underflow)。常见处理方式是把负数结果加上,保证结果始终在范围内。
这相当于所有的操作都是对"2的某次方"取模:
无论哪种情况,它都会触发一个可以检查的特殊标志。但通常,当人们明确使用无符号整数时,他们预期会有这种行为。
有符号整型
有符号整数通过将最高位用来表示数字的符号来支持存储负值,这种方式与浮点数的处理方式相似。这使得可表示的非负数的范围减半:现在最大可能的32位整数是,而不是。但是,负值的编码方式与浮点数并不完全相同。
计算机工程师比程序员更懒,这不仅源于他们本能的简化欲望,也是为了节省晶体管空间。这可以通过重用已有的用于其他操作的电路来实现,这就是他们在设计有符号整数格式时的目标:
- 对于位有符号整数类型,范围在之内的所有数的编码方式与它们在无符号二进制表示中的编码方式保持一致。
- 所有在范围内的数都在“正数”范围之后顺序编码。即从开始,该值的编码为;到结束,其编码为。
所有的负数都被编码成它们被减去的结果,这种操作被称为二进制补码(two’s complement)。
这里代表按位取反,也可以认为是从中减去。
以下是一些关于有符号整型的特点:
- 所有的正数和零保持和二进制表示一样;
- 所有的负数最高位设为一;
- 负数比正数多一个:这是因为0的存在,正数和0加在一起的数量与负数相同;
- 对于
int
类型,如果你对加1,则结果为,表示为1000...0000
; - 知道一个正数
x
的二级制表示,你就可以得到-x
的表示~x + 1
(取反加1); -1
被表示为~1 + 1 = 11111110 + 00000001 = 11111111
;-42
被表示为~42 + 1 = 11010101 + 00000001 = 11010110
;-1 = 11111111
之后是0 = -1 + 1 = 11111111 + 00000001 = 00000000
;
这种编码方式的优点是你无需做任何转换就能将无符号整数转换为有符号整数(除了可能需要检查溢出),且大多数操作可以复用同样的硬件电路。
然而,需要注意的是有符号整数的溢出。尽管它们几乎始终与无符号整数的溢出方式相同(INT_MAX + 1 == INT_MIN
),但编程语言通常将有符号整型的溢出的可能性视为未定义的行为。所以如果你需要让整数变量溢出,将它们转换为无符号整数,反正转换是“免费”的。
练习题:对于std::abs
函数(该函数的功能是返回其参数的绝对值),唯一一个会产生错误结果的整数值是什么?并会产生什么样的结果? (答案:整数最小值。对8位整型而言,是-128,其绝对值128无法用8位整型表示。所以对整数最小值取绝对值的结果是未定义的,可能仍然返回整数最小值,导致绝对值为负数的错误)
整数类型
整数有不同的尺寸,但功能大致相同。
Bits | Bytes | Signed C type | Unsigned C Type | Assembly |
---|---|---|---|---|
8 | 1 | signed char |
unsigned char |
byte |
16 | 2 | short |
unsigned short |
word |
32 | 4 | int |
unsigned int |
dword |
64 | 8 | long long |
unsigned long long |
qword |
在计算机中,整数是以位的形式存储的。这些位可以按从左到右或从右到左的顺序存储,这种顺序即为字节序(endianness)。而这种存储顺序在不同的计算机架构上可能会有所不同:
- 小端(Little-endian):是指数据的低位字节(较小的一端)放在内存的低地址上,而数据的高位字节放在高地址上。例如,数字的二进制形式是101010。小端表示法下,它的二进制表示仍然是101010,但最低有效位(右边的0)在最低的内存地址。
- 大端(Big-endian):则是正好相反,数据的高位字节(较大的一端)放在内存的低地址上,低位字节放在高地址上。本文中之前的所有例子都按照这种方式进行存储。
在大多数情况下,这两种存储方式选择哪种并无太大差别,重要的是在一个项目或一种环境下坚持使用同一种方式。但在一些特定情况下,它们各自优势明显:
- Little-endian的优势在于,当你需要将数据从大类型(比如
long long
)转换为小类型(比如int
)时,你只需加载较少的字节,这在大多数情况下意味着无需做任何操作。这得益于寄存器别名(register aliasing)技术,比如,eax
指向的就是rax
的前4个字节,因此转换基本上是“免费”的。 - 相反地,Big-endian方式的优势在于,加载数据时,高位字节首先被加载,理论上,像数据比较和打印等由高到低的操作会更快。并且,你可以通过只加载第一个字节来执行一些检查操作,比如判断一个数字是否为负。
big-endian字节序被认为更为"自然",因为这是我们在纸上写二进制数的方式,即高位在前,低位在后。然而,little-endian在转换数据类型的速度上更有优势。所以大多数硬件默认使用little-endian, 然而也有一些CPU是"双端模式"(bi-endian),可以根据需要在big-endian和little-endian之间切换。
128-bit 整数
有时我们需要将两个64位整数相乘以获取128位整数——通常用作临时值,并立即被模化为64位整数。
由于处理器中没有128位的寄存器来容纳这个结果,所以我们需要特殊的方式来处理这个返回结果。 在这种情况下,mul
指令除了常规的mul r r
形式(它将存储在寄存器中的值相乘,结果的低半部分保留在原寄存器中),还有另外一种mul r
模式。 在这个mul r
模式中,指令将寄存器rax
中的值与操作数相乘,结果被写入两个寄存器,其中低64位数会存入rax
中,高64位数会存入rdx
中。
; input: 64-bit integers a and b, stored in rsi and rdi |
某些编译器有一个单独的类型支持此操作。在GCC和Clang中,可用__int128
表示:
void prod(int64_t a, int64_t b, __int128 *c) { |
它的典型用例是立即提取乘法的较低部分或较高部分,随后就不再使用它:
__int128_t x = 1; |
在除了乘法以外的所有操作中,128位整数通常被作为两个寄存器来处理。这使得拥有一个完全成熟的128位类型变得有些奇怪,因此对它的支持有限,除了基本的算术操作。例如:
__int128_t add(__int128_t a, __int128_t b) { |
会被编译成:
add: |
处理大于字长度乘法的类似机制在其他平台上也有提供。例如,Arm提供了mulhi
和mullo
指令,这两个指令可以分别返回乘法的高位部分和低位部分。另外,x86的SIMD扩展也提供了类似的32位指令。
备注
[1] 请注意,从技术上讲,char
、unsigned char
和signed char
是三种不同的类型。根据C语言的标准,char
是有符号还是无符号,由该语言的实现决定(在大多数编译器中,它是有符号的)。