基本数据类型回顾：数字和字符串

Posted on 2022-10-01

肖像2018facebook.jpg

计算机编程从将数据组织成数据结构开始。在几乎所有情况下，我们都使用字符串或数字。了解这些构建块对于成为专家级程序员至关重要。

字

我们经常使用固定的内存块来组织数据。当这些块相对较小（例如，8 位、16 位、32 位、64 位）时，我们通常称它们为“字”。

“字”的概念很重要，因为处理器不会对任意数据类型进行操作。出于实际原因，处理器希望数据适合具有某些固定大小的硬件寄存器（通常为 64 位寄存器）。大多数现代处理器可容纳具有快速指令的 8 位、16 位、32 位和 64 位字。内存访问的粒度通常不小于“字节”（8 位），因此从某种意义上说，字节是最小的实用字。

可变长度数据结构（如字符串）可能由可变数量的单词组成。从历史上看，字符串是由字节列表组成的，但其他替代方案很常见（例如，16 位或 32 位字）。

布尔值

最简单的类型可能是布尔类型。布尔值可以采用 false 或 true 值。尽管单个位足以表示布尔值，但通常使用整个字节（或更多）。
我们可以否定一个布尔值：真值变成假值，反之亦然。还有二进制操作：

  • 当且仅当两个输入都为假时，两个布尔值之间的 OR 运算的结果为假。 OR 操作经常被注意到| .例如， 1 | 0 == 1我们使用符号==表示两个值之间相等的约定。
  • 当且仅当两个输入都为真时，两个布尔值之间的 AND 运算结果为真。 AND 操作通常记为& 。例如， 1 & 1 == 1 。
  • 当且仅两个输入的值不同时，异或运算的结果为真。 XOR 操作经常被记下^ 。例如， 1 ^ 1 == 0 。
  • 当且仅当第一个布尔值为真而第二个布尔值为假时，两个布尔值之间的 AND NOT 运算的结果为真。

整数

在布尔类型之后，整数数据类型可能是软件和硬件中支持最广泛的数据类型。我们经常用数字表示整数。例如，整数 1234 有 4 个十进制数字。通过扩展，我们在计算机中使用称为位的“二进制”数字。我们经常使用0b前缀使用二进制表示法来编写整数。例如，整数0b10是 2，整数0b10110等于2^1+2^2+2^4或 22。在前缀0b之后，我们从最高有效位开始枚举位值。我们也可以使用带有0x前缀的十六进制（以 16 为基数）表示法：在这种情况下，我们在列表0, 1, 2, 3,..., 9, A, B, C, D, E, F 。这些数字的值是0, 1, 2, 3,..., 9, 10, 11, 12, 13, 14, 16 。对于用字母表示的数字，我们可以使用小写或大写。因此，数字0x5A等于5 * 16 + 10或十进制的 90。处理二进制值时，十六进制表示法很方便：一位表示 4 位值，两位表示 8 位值，依此类推。

我们可以使用公式ceil(log(x+1))计算整数的位数，其中对数是您感兴趣的底数（例如，底数 2），其中ceil是上限函数： ceil(x)返回不小于x的最小整数。具有d1位的整数和具有d2位的整数之间的乘积具有d1+d2-1位或d1+d2位。为了说明，让我们考虑两个具有三位数字的整数之间的乘积。以 10 为底，最小乘积是 100 乘以 100 是 10,000，因此需要 5 位数字。最大的乘积是 999 乘以 999 或 998,001 所以 6 位数。

为了速度或方便，我们可能会使用固定位数。鉴于我们使用二进制计算机，我们可能会使用二进制数字。我们还需要一种表示数字符号（负数和正数）的方法。

无符号整数

可能最简单的数字类型是无符号整数，我们使用固定位数来表示非负整数。大多数处理器支持无符号整数的算术运算。在这种情况下，术语“无符号”等同于“非负”：整数可以是零或正数。

我们可以使用按位逻辑运算对二进制整数进行运算。例如， 0b101和0b1100之间的按位与是0b100 。按位或为0b1111 。按位异或（异或）是0b1001 。

2 的幂 (1, 2, 4, 8,…) 是唯一在其二进制表示中具有单个 1 位的0b10 0b100 0b1 0b1000 ）。 2 (1,3,7,…) 的幂之前的数字是由最低有效位置（ 0b1等） 0b1111的连续 1 位0b11的0b111 。 2 的幂的一个独特特征是它们与前一个整数的按位与为零：例如，4 AND 3 为零，8 AND 7 为零，等等。

例如，在 Go 编程语言中，我们有 8 位、16 位、32 位和 64 位无符号整数类型： uint8 、 uint16 、 uint32 、 uint64 。它们可以表示从 0 到（但不包括）2 的 8、16、32 和 64 次方的所有数字。例如，一个 8 位无符号整数可以表示从 0 到 255（含）的所有整数。

因为我们选择使用固定数量的位，所以我们只能表示一个整数范围。算术运算的结果可能超出范围（溢出）。例如，255 加 2 是 257：虽然两个输入（255 和 2）都可以使用 8 位无符号整数表示，但结果超出了范围。

关于乘法，两个 8 位无符号整数的乘积最多为 65025，可以用一个 16 位无符号整数表示。通常情况下，两个n位整数的乘积可以用2n位来表示。反过来是不正确的：给定的2n位整数不是两个n位整数的乘积。随着n变大，所有2n位整数中只有一小部分可以写成两个n位整数的乘积，这个结果首先由 Erdős 证明。

通常，算术运算是“模”二的幂。也就是说，一切都好像我们使用无限精度整数进行计算，然后我们只保留除以 2 的幂的（正）余数。

让我们详细说明。给定两个整数a和b （ b非零），有唯一的整数d和r ，其中r在[0,b)中，使得a = d * b + r 。整数r是余数，整数d是商。

欧几里得除法引理告诉我们商和余数存在并且是唯一的。我们可以检查唯一性。假设有另一对这样的整数（ d'和r' ）， a = d' * b + r' 。我们可以检查如果d'等于d ，那么我们必须有r'等于r ，反之，如果r'等于r ，那么d'等于d 。假设r'大于r （如果不是，只需反转参数）。然后，通过减法，我们得到0 = (d'-d)*b + (r'-r) 。我们必须让r'-r在[0,b)中。如果d'-d是负数，那么我们有(d-d')*b = (r'-r) ，但这是不可能的，因为r'-r在[0,b)而(d-d')*b大于或等于b 。当d'-d为正时，类似的论点也有效。

在我们的例子中，除数 ( b ) 是 2 的幂。当分子 ( a ) 为正时，余数相当于选择最低有效位。例如，65（或0b1000001 ）除以 64 的余数是 1。

在考虑无符号算术时，通常认为我们只保留最终结果的最低有效位（8、16、32 或 64）会有所帮助。因此，如果我们取 255 并加上 2，我们得到 257，但作为一个 8 位无符号整数，我们得到数字 1。因此，使用uint8类型的整数，我们有255 + 2是 1 ( 255 + 2 == 1 ）。 2 的幂本身为零：作为uint8整数，256 等于 0。如果我们减去两个数字并且值将是负数，我们有效地“环绕”： uint8算术中的 10 – 20 是 (-10) 除以 256 的正余数，即 246。考虑负数的另一种方法是我们可以根据需要多次添加 2 的幂（比如 256）（大小其值实际上为零），直到我们得到一个介于 0 和 2 的幂之间的值。因此，如果我们必须将1-5*250计算为 8 位整数，我们取结果 (-1249) 并根据需要多次添加 256：我们有-1249+5*256是 31，一个介于0 和 256。因此1-5*250是 31 作为无符号 8 位数字。

我们有0-1 ，作为一个 8 位数字，是 255 或0b11111111 。 0-2是0-3是 253 等等。 考虑整数集……

 -1024, -1023,..., -513, -512, -511, ..., -1, 0, 1,...255, 256, 257,...

作为 256 位整数，它们被映射到

0, 255,... .1, 0, 255, ..., 255, 0, 1,...255, 0, 1,...

乘以 2 的幂相当于将位左移，可能会丢失最左边的位。例如， 17 是0b10001 。将它乘以 4，我们得到0b1000100或 68。如果我们将 17 乘以 4，我们将得到0b100010000 ，或者，作为一个 8 位整数， 0b10000 。也就是说，作为 8 位无符号整数，我们有17 * 16是 16。因此我们有17 * 16 == 1 * 16 。

两个非零整数的乘积可能为零。例如， 16*16作为 8 位整数为零。只有当两个整数都可以被 2 整除时才会发生这种情况。两个奇数的乘积一定是奇数。

如果两个数字的最大公约数是 1，我们说这两个数字是“互质的”。奇数是 2 的幂的互质数。甚至整数也不会与 2 的幂互质。

当使用有限位算术将非零整数乘以奇数时，我们永远不会得到零。因此，例如，当且仅当使用固定位无符号整数时x为零时，作为 8 位整数的3 * x为零。这意味着当且仅当x和y相等时， 3 * x等于3 * y 。因此，我们有以下 Go 代码将打印出从 0 到 255 的所有值，而不重复：

 for i:=uint8(1); i != 0; i++ { fmt.Println(3*i) }

将整数乘以奇数会置换它们。

如果您考虑奇整数的幂，您同样永远不会得到零结果。然而，你最终可能会获得成为其中一员的力量。例如，作为一个 8 位无符号整数，3 的 64 次方是 1。这个数字 (64) 有时称为 3 的“阶”。由于这是最小的指数，因此结果为 1，我们有所有 63 次幂都给出了不同的结果。我们可以如下展示这个结果。假设 3 的p等于 3 的q次幂，并且不失一般性地假设p>q ，那么我们有3的pq次幂必须是 1，通过检查。如果p和q都小于 64，那么 b pq也必须如此，这是一个矛盾。此外，我们可以检查在达到顺序后奇数的幂是否重复：我们有 3 的 64 次方是 1，3 的 65 次方是 3，3 的 66 次方是 9，所以向前。因此，任何奇数的阶必须除以 2 的幂（例如，256）。

奇数的阶数可以有多大？我们可以检查奇整数的所有幂都必须是奇整数，并且只有 128 个不同的 8 位整数。因此，8 位奇数的阶数最多为 128。相反，欧拉定理告诉我们，任何奇数的奇数次方（例如，3 的 128 次方）必须是 1。因为奇数的幂值在达到阶数后循环重复，所以对于 8 位无符号整数，任何奇数的阶数必须除以 128。通常，无论字的位宽如何，奇数的阶必须是 2 的幂。

给定两个非零无符号整数a和b ，我们期望a+b>max(a+b)但只有在没有溢出时才成立。当且仅当存在溢出时，我们使用有限位无符号算术得到a+b<min(a+b) 。我们可以使用以下任一条件检查溢出： a+b<a和a+b<b 。

通常，计算机可以对两个整数进行的最昂贵的操作之一就是将它们相除。除法可能需要比乘法多几倍的周期，而乘法通常比简单的加法或减法昂贵很多倍。但是，除以 2 的幂和乘以 2 的幂的成本很低：我们可以通过右移位来计算无符号整数除法的整数商。例如，整数 7 (0b111) 除以 2 是 0b011 或 3。我们可以进一步将 7 (0b111) 除以 4 得到 0b001 或 1。整数余数通过选择将移出的位给出：余数7 除以 4 是 7 AND 0b11 或 0b11。除以二的余数只是最低有效位。偶数整数的特征是零作为最低有效位。同样，乘以 2 的幂只是左移：整数 7 (0b111) 乘以 2 是 14 (0b1110)。更一般地，当除数固定时，优化编译器可以生成用于计算余数和商的有效代码。通常，它至少涉及乘法和移位。

给定一个整数x ，如果x * y == 1 ，我们说y是它的乘法逆元。我们有每个奇整数都有一个乘法逆元，因为乘以一个整数会创建所有整数的排列。我们可以使用牛顿法计算这个乘法逆。也就是说，我们从猜测开始，然后从猜测中得到更好的猜测，依此类推，直到我们自然地收敛到正确的值。所以我们需要一些公式f(y) ，这样我们就可以重复调用y = f(y)直到y收敛。一个有用的递归公式是f(y) = y * (2 - y * x) 。您可以验证如果y是x的乘法逆元，则f(y) = y 。假设y不是完全相反的，假设x * y = 1 + z * p对于某个奇数整数z和某个 2 p的幂。如果 2 的幂是（比如说）8，那么它会告诉您y是前三位的乘法逆元。我们得到x * f(y) = x * y * (2 - y * x) = 2 + 2 * z * p - (1 - 2 * z * p + z * z * p * p) = 1 - z * z * p * p 。从这个结果我们可以看出，如果y是前n位的乘法逆，那么 f(y) 是2n位的乘法逆。也就是说，如果y是“前n位”的倒数，则f(y)是“前2n位”的倒数。每次调用递推公式时，我们都会将精度加倍。这意味着我们可以快速收敛于逆。

我们最初对y的猜测应该是什么？如果我们使用 3 位字，那么每个数字都是它的倒数。所以从y = x开始会给我们 3 位的准确度，但我们可以做得更好： ( 3 * x ) ^ 2提供 5 位的准确度。以下 Go 程序验证了该声明：

 package main import "fmt" func main() { for x := 1; x < 32; x += 2 { y := (3 * x) ^ 2 if (x*y)&0b11111 != 1 { fmt.Println("error") } } fmt.Println("Done") }

观察我们如何使用表达式&0b11111捕获 5 个最低有效位：它是按位逻辑与运算。

从 5 位开始，第一次调用递归公式给出 10 位，然后是 20 位用于第二次调用，然后是 40 位，然后是 80 位。因此，我们需要为 16 位值调用我们的递推公式 2 次，为 32 位值调用 3 次，为 64 位值调用 4 次。函数FindInverse64计算奇整数的 64 位乘法逆：

 func f64(x, y uint64) uint64 { return y * (2 - y*x) } func FindInverse64(x uint64) uint64 { y := (3 * x) ^ 2 // 5 bits y = f64(x, y) // 10 bits y = f64(x, y) // 20 bits y = f64(x, y) // 40 bits y = f64(x, y) // 80 bits return y }

我们有FindInverse64(271) * 271 == 1 。重要的是，如果提供的整数是偶数，它会失败。

我们可以使用乘法逆元用乘法代替奇数除法。也就是说，如果您预先计算FindInverse64(3) ，那么您可以通过计算乘积来计算任何三的倍数除以三：例如FindInverse64(3) * 15 == 5 。

当我们在字节数组中存储多字节值（例如无符号整数）时，我们可以使用以下两种约定之一：小端和大端。 little-endian 和 big-endian 变体仅在字节顺序上有所不同：我们要么从最低有效字节（little endian）开始，要么从最高有效字节（big endian）开始。让我们考虑整数 12345。一个十六进制值，它是 0x3039。如果我们将其存储为两个字节，我们可以将其存储为字节值 0x30 后跟字节值 0x39（大端），或者相反（0x39 后跟 0x30）。大多数现代系统都默认使用 little-endian 约定，而 big-endian 系统相对较少。在实践中，我们很少需要关心系统的字节顺序。

有符号整数和二进制补码

给定无符号整数，我们如何添加对有符号整数的支持？乍一看，很想为这个标志预留一点。因此，如果我们有 32 位，我们可能会使用一位来指示值是正数还是负数，然后我们可以使用 31 位来存储整数的绝对值。

尽管这种符号位方法是可行的，但它也有缺点。第一个明显的缺点是有两个可能的零值： +0和-0 。另一个缺点是，与无符号整数相比，它使有符号整数的值完全不同：理想情况下，我们希望对无符号整数进行操作的硬件指令“只对有符号整数起作用”。

因此，现代计算机使用二进制补码表示法来表示有符号整数。为了简化说明，我们考虑 8 位整数。无论使用有符号整数还是无符号整数，我们都以相同的方式表示所有正整数，直到范围的一半（8 位字为 127）。仅当设置了最高有效位时，我们才有所不同：对于有符号整数，就好像从除最高有效位之外的所有位派生的无符号值减去范围的一半（128）。例如，作为 8 位有符号值，0b11111111 为 -1。事实上，忽略最高位，我们有 0b1111111 或 127，减去 128，我们得到 -1。

二进制 未签名 签
0b00000000 0 0
0b00000001 1 1
0b00000010 2 2
0b01111111 127 127
0b10000000 128 -128
0b10000001 129 -127
0b11111110 254 -2
0b11111111 255 -1

在 Go 中，您可以将无符号整数“转换”为有符号整数，反之亦然：Go 保持二进制值不变，但它只是将值重新解释为无符号和有符号整数。如果我们执行以下代码，我们就有x==z ：

 x := uint16(52429) y := int16(x) z := uint16(y)

方便的是，无论我们计算两个值之间的乘法、加法还是减法，无论我们将这些位解释为有符号值还是无符号值，结果都是相同的（二进制）。因此我们可以使用相同的硬件电路。

二进制补码表示法的一个缺点是不能安全地否定最小的负值（在 8 位情况下为 -128）。事实上，数字 128 不能用 8 位有符号整数表示。这种不对称是不可避免的，因为我们有三种类型的数字：零、负值和正值。然而，我们有偶数个二进制值。

与无符号整数一样，我们可以（左右）移动有符号整数。左移的作用类似于位级别的无符号整数。我们有那个

x := int8(1)
(x << 1) == 2
(x << 7) == -128

但是，右移对有符号和无符号整数的工作方式不同。对于无符号整数，我们从左移零；对于有符号整数，我们要么移入零（如果整数是正数或零）或移入一（如果整数和负数）。我们用一个例子来说明这种行为：

 x := int8(-1) (x >> 1) == -1 y := uint8(x) y == 255 (y >> 1) == 127

当有符号整数为正时，除以 2 的幂或右移具有相同的结果（ 10/4 == (10>>2) ）。但是，当整数为负时，只有当负整数能被 2 的幂整除时才成立。当负整数不能被 2 的幂整除时，则移位比除法小 1，如以下代码所示：

 x := int8(-10) (x / 4) == -2 (x >> 2) == -3

浮点数字

在计算机上，实数通常由二进制浮点数近似：一个固定宽度的整数m （有效数字）乘以 2，得到整数指数p ： m * 2**p其中2**p表示数字 2提高到p次方。添加有符号位，以便正零和负零都可用。今天的大多数系统都遵循 IEEE 754 标准，这意味着您可以获得跨编程语言和操作系统的一致结果。因此，如果你在 Linux 下用 C++ 实现你的软件，而其他人在 Windows 下用 C# 实现它，这并不重要：如果你们都有最新的系统，在进行基本算术和平方根运算时，你可以预期相同的数值结果。

正正常双精度浮点数是二进制浮点数，其中 53 位整数m在区间[2**52,2**53)中，同时被解释为[1,2)通过将其虚拟除以2**52 ，其中 11 位指数p的范围从-1022到+1023 。因此，我们可以表示2**-1022到但不包括2**1024之间的所有值。一些小于2**-1022的值可以表示为次正规值：它们使用具有值2**-1022的特殊指数代码，然后将有效位解释为区间[0,1)中的值。

在 Go 中， float64数字可以表示由大约-1.8 * 10**308到1.8 *10**308的 15 位有效数字组成的所有十进制数。反之则不然：只有 15 位精度来区分任何两个浮点数是不够的：我们可能需要多达 17 位。

float32类型类似。它可以表示2**-126到但不包括2**128之间的所有数字；对一些小于2**-126 （次正规）的数字进行特殊处理。 float32类型可以准确地表示由 6 位十进制有效位组成的所有十进制数，但通常需要 9 位来唯一标识一个数字。

浮点数还包括正无穷和负无穷，以及特殊的非数字值。它们由保留的指数值标识。

数字通常被序列化为字符串中的十进制数字，然后由接收器解析回来。但是，通常不可能将十进制数转换为二进制浮点数：数字0.2没有作为二进制浮点数的精确表示。但是，您应该期望系统选择最佳近似值： 7205759403792794 * 2**-55作为float64数字（或大约0.20000000000000001110 ）。如果初始数字是float64 （例如），您应该期望保留确切的值：它将在 Go 中按预期工作。

字符串

最早的字符串标准之一是 ASCII：它在 1960 年代初首次指定。 ASCII 标准仍然很流行。每个字符都是一个字节，最高有效位设置为零。因此只有 128 个不同的 ASCII 字符。对于像编程这样的简单任务，它通常就足够了。不幸的是，ASCII 标准最多只能表示 128 个字符：远远少于需要的。

出现了许多不同的标准来表示软件中的字符。多种不兼容格式的存在使得可互操作的本地化软件的生产具有挑战性。

工程师在 1980 年代后期开发了 Unicode，试图提供一个通用标准。最初，人们认为每个字符使用 16 位就足够了，但这种看法是错误的。 Unicode 标准被扩展为包含多达 1,114,112 个字符。所有可能的字符中只有一小部分已被分配，但随着时间的推移，随着每个 Unicode 修订版分配更多。 Unicode 标准是 ASCII 标准的扩展：前 128 个 Unicode 字符与 ASCII 字符匹配。

由于最初期望 Unicode 适合 16 位空间，因此在 1996 年发布了一种基于 16 位字 (UTF-16) 格式的格式。它可以使用每个字符 16 位或 32 位。 UTF-16 格式被 Java 等编程语言采用，并成为 Windows 下的默认格式。不幸的是，UTF-16 在字节级别上不向后兼容 ASCII。一种与 ASCII 兼容的格式在 2003 年提出并正式化：UTF-8。随着时间的推移，UTF-8 被广泛用于文本交换格式，例如 JSON、HTML 或 XML。 Go、Rust 和 Swift 等编程语言默认使用 UTF-8。两种格式（UTF-8 和 UTF-16）都需要验证：并非所有字节数组都是有效的。 UTF-8 格式的验证成本更高。

ASCII 字符在 UTF-8 中需要一个字节，在 UTF-16 中需要两个字节。 UTF-16 格式可以用两个字节来表示除 emojis 等补充字符外的所有字符。 UTF-8 格式对拉丁字母、希伯来字母和阿拉伯字母使用两个字节，对亚洲字符使用三个字节，对补充字符使用 4 个字节。

UTF-8 将值编码为一到四个字节的序列。我们将序列的第一个字节称为前导字节；前导字节的最高有效位表示序列的长度：

  • 如果最高有效位为零，则我们有一个字节序列（ASCII）。
  • 如果三个最高有效位是 0b110，我们有一个两字节序列。
  • 如果四个最高有效位是 0b1110，我们有一个三字节序列。
  • 最后，如果五个最高有效位是 0b11110，我们就有一个四字节序列。
    序列中前导字节之后的所有字节都是连续字节，它们的最高有效位必须为 0b10。除了所需的最高有效位外，字符的数值（介于 0 到 1,114,112 之间）的存储方式是从最高有效位（在前导字节中）开始，然后是其他连续字节中的次要有效位。

在 UTF-16 格式中，0x0000-0xD7FF 和 0xE000-0xFFFF 中的字符存储为单个 16 位字。 0x010000 到 0x10FFFF 范围内的字符需要两个 16 位字，称为代理对。该对中的第一个字在 0xd800 到 0xdbff 范围内，而第二个字在 0xdc00 到 0xdfff 范围内。字符值由两个字的 10 个最低有效位组成，使用第二个字作为最低有效位，并将 0x10000 添加到结果中。 UTF-16 格式有两种类型。在 little-endian 变体中，每个 16 位字都使用第一个字节中的最低有效位进行存储。在 big-endian 变体中情况正好相反。

使用 ASCII 时，以随机顺序访问字符相对容易。对于 UTF-16，如果我们假设没有补充字符是可能的，但由于某些字符可能需要 4 个字节，而其他 2 个字节，因此不可能在不访问先前内容的情况下直接通过其索引找到一个字符。 UTF-8 通常也不是随机访问的。

软件通常取决于所选的语言环境：例如，美国英语、加拿大法语等。对字符串进行排序取决于语言环境。在不知道语言环境的情况下，通常不可能对字符串进行排序。但是，可以按字典顺序将字符串排序为字节序列 (UTF-8) 或 16 位字序列 (UTF-16)。使用 UTF-8 时，结果是基于字符数值的字符串排序。

原文： https://lemire.me/blog/2022/09/30/a-review-of-elementary-data-types-numbers-and-strings/