閱讀(672) 書簽贊(1) 我要糾錯(cuò)

C++數(shù)字編碼

2023-09-20 09:23 更新

數(shù)字編碼 *

Note

在本書中，標(biāo)題帶有的 * 符號(hào)的是選讀章節(jié)。如果你時(shí)間有限或感到理解困難，可以先跳過，等學(xué)完必讀章節(jié)后再單獨(dú)攻克。

3.3.1 原碼、反碼和補(bǔ)碼

在上一節(jié)的表格中我們發(fā)現(xiàn)，所有整數(shù)類型能夠表示的負(fù)數(shù)都比正數(shù)多一個(gè)，例如 byte 的取值范圍是 [?128,127] 。這個(gè)現(xiàn)象比較反直覺，它的內(nèi)在原因涉及到原碼、反碼、補(bǔ)碼的相關(guān)知識(shí)。

首先需要指出，數(shù)字是以“補(bǔ)碼”的形式存儲(chǔ)在計(jì)算機(jī)中的。在分析這樣做的原因之前，我們首先給出三者的定義。

原碼：我們將數(shù)字的二進(jìn)制表示的最高位視為符號(hào)位，其中 0 表示正數(shù)，1 表示負(fù)數(shù)，其余位表示數(shù)字的值。
反碼：正數(shù)的反碼與其原碼相同，負(fù)數(shù)的反碼是對(duì)其原碼除符號(hào)位外的所有位取反。
補(bǔ)碼：正數(shù)的補(bǔ)碼與其原碼相同，負(fù)數(shù)的補(bǔ)碼是在其反碼的基礎(chǔ)上加 1 。

圖 3-4 展示了原碼、反碼和補(bǔ)碼之間的轉(zhuǎn)換方法。

原碼、反碼與補(bǔ)碼之間的相互轉(zhuǎn)換

圖 3-4 原碼、反碼與補(bǔ)碼之間的相互轉(zhuǎn)換

「原碼 true form」雖然最直觀，但存在一些局限性。一方面，負(fù)數(shù)的原碼不能直接用于運(yùn)算。例如在原碼下計(jì)算 1+(?2) ，得到的結(jié)果是 ?3 ，這顯然是不對(duì)的。

\begin{matrix} 1 + (? 2) \\ \to 0000 0001 + 1000 0010 \\ = 1000 0011 \\ \to ? 3 \end{matrix}

為了解決此問題，計(jì)算機(jī)引入了「反碼 1's complement code」。如果我們先將原碼轉(zhuǎn)換為反碼，并在反碼下計(jì)算 1+(?2) ，最后將結(jié)果從反碼轉(zhuǎn)化回原碼，則可得到正確結(jié)果 ?1 。

\begin{matrix} 1 + (? 2) \\ \to 0000 0001 (原碼) + 1000 0010 (原碼) \\ = 0000 0001 (反碼) + 1111 1101 (反碼) \\ = 1111 1110 (反碼) \\ = 1000 0001 (原碼) \\ \to ? 1 \end{matrix}

另一方面，數(shù)字零的原碼有 +0 和 ?0 兩種表示方式。這意味著數(shù)字零對(duì)應(yīng)著兩個(gè)不同的二進(jìn)制編碼，其可能會(huì)帶來歧義。比如在條件判斷中，如果沒有區(qū)分正零和負(fù)零，則可能會(huì)導(dǎo)致判斷結(jié)果出錯(cuò)。而如果我們想要處理正零和負(fù)零歧義，則需要引入額外的判斷操作，其可能會(huì)降低計(jì)算機(jī)的運(yùn)算效率。

\begin{matrix} + 0 & \to 0000 0000 \\ ? 0 & \to 1000 0000 \end{matrix}

與原碼一樣，反碼也存在正負(fù)零歧義問題，因此計(jì)算機(jī)進(jìn)一步引入了「補(bǔ)碼 2's complement code」。我們先來觀察一下負(fù)零的原碼、反碼、補(bǔ)碼的轉(zhuǎn)換過程：

\begin{matrix} ? 0 \to & 1000 0000 (原碼) \\ = & 1111 1111 (反碼) \\ = 1 & 0000 0000 (補(bǔ)碼) \end{matrix}

在負(fù)零的反碼基礎(chǔ)上加 1 會(huì)產(chǎn)生進(jìn)位，但 byte 類型的長(zhǎng)度只有 8 位，因此溢出到第 9 位的 1 會(huì)被舍棄。也就是說，負(fù)零的補(bǔ)碼為 00000000 ，與正零的補(bǔ)碼相同。這意味著在補(bǔ)碼表示中只存在一個(gè)零，正負(fù)零歧義從而得到解決。

還剩余最后一個(gè)疑惑：byte 類型的取值范圍是 [?128,127] ，多出來的一個(gè)負(fù)數(shù) ?128 是如何得到的呢？我們注意到，區(qū)間 [?127,+127] 內(nèi)的所有整數(shù)都有對(duì)應(yīng)的原碼、反碼和補(bǔ)碼，并且原碼和補(bǔ)碼之間是可以互相轉(zhuǎn)換的。

然而，補(bǔ)碼 10000000 是一個(gè)例外，它并沒有對(duì)應(yīng)的原碼。根據(jù)轉(zhuǎn)換方法，我們得到該補(bǔ)碼的原碼為 00000000 。這顯然是矛盾的，因?yàn)樵撛a表示數(shù)字 0 ，它的補(bǔ)碼應(yīng)該是自身。計(jì)算機(jī)規(guī)定這個(gè)特殊的補(bǔ)碼 10000000 代表 ?128 。實(shí)際上，(?1)+(?127) 在補(bǔ)碼下的計(jì)算結(jié)果就是 ?128 。

\begin{matrix} (? 127) + (? 1) \\ \to 1111 1111 (原碼) + 1000 0001 (原碼) \\ = 1000 0000 (反碼) + 1111 1110 (反碼) \\ = 1000 0001 (補(bǔ)碼) + 1111 1111 (補(bǔ)碼) \\ = 1000 0000 (補(bǔ)碼) \\ \to ? 128 \end{matrix}

你可能已經(jīng)發(fā)現(xiàn)，上述的所有計(jì)算都是加法運(yùn)算。這暗示著一個(gè)重要事實(shí)：計(jì)算機(jī)內(nèi)部的硬件電路主要是基于加法運(yùn)算設(shè)計(jì)的。這是因?yàn)榧臃ㄟ\(yùn)算相對(duì)于其他運(yùn)算（比如乘法、除法和減法）來說，硬件實(shí)現(xiàn)起來更簡(jiǎn)單，更容易進(jìn)行并行化處理，運(yùn)算速度更快。

請(qǐng)注意，這并不意味著計(jì)算機(jī)只能做加法。通過將加法與一些基本邏輯運(yùn)算結(jié)合，計(jì)算機(jī)能夠?qū)崿F(xiàn)各種其他的數(shù)學(xué)運(yùn)算。例如，計(jì)算減法 a?b 可以轉(zhuǎn)換為計(jì)算加法 a+(?b) ；計(jì)算乘法和除法可以轉(zhuǎn)換為計(jì)算多次加法或減法。

現(xiàn)在我們可以總結(jié)出計(jì)算機(jī)使用補(bǔ)碼的原因：基于補(bǔ)碼表示，計(jì)算機(jī)可以用同樣的電路和操作來處理正數(shù)和負(fù)數(shù)的加法，不需要設(shè)計(jì)特殊的硬件電路來處理減法，并且無須特別處理正負(fù)零的歧義問題。這大大簡(jiǎn)化了硬件設(shè)計(jì)，提高了運(yùn)算效率。

補(bǔ)碼的設(shè)計(jì)非常精妙，因篇幅關(guān)系我們就先介紹到這里，建議有興趣的讀者進(jìn)一步深度了解。

3.3.2 浮點(diǎn)數(shù)編碼?

細(xì)心的你可能會(huì)發(fā)現(xiàn)：int 和 float 長(zhǎng)度相同，都是 4 bytes，但為什么 float 的取值范圍遠(yuǎn)大于 int ？這非常反直覺，因?yàn)榘蠢碚f float 需要表示小數(shù)，取值范圍應(yīng)該變小才對(duì)。

實(shí)際上，這是因?yàn)楦↑c(diǎn)數(shù) float 采用了不同的表示方式。記一個(gè) 32-bit 長(zhǎng)度的二進(jìn)制數(shù)為：

b_{31} b_{30} b_{29} \dots b_{2} b_{1} b_{0}

根據(jù) IEEE 754 標(biāo)準(zhǔn)，32-bit 長(zhǎng)度的 float 由以下三個(gè)部分構(gòu)成。

符號(hào)位 S ：占 1 bit ，對(duì)應(yīng) $b_{31}$ 。
指數(shù)位 E ：占 8 bits ，對(duì)應(yīng) $b_{30} b_{29} \dots b_{23}$ 。
分?jǐn)?shù)位 N ：占 23 bits ，對(duì)應(yīng) $b_{22} b_{21} \dots b_{0}$ 。
。

二進(jìn)制數(shù) float 對(duì)應(yīng)的值的計(jì)算方法：

val = (? 1)^{b_{31}} \times 2^{{(b_{30} b_{29} \dots b_{23})}_{2} ? 127} \times {(1 . b_{22} b_{21} \dots b_{0})}_{2}

轉(zhuǎn)化到十進(jìn)制下的計(jì)算公式：

val = (? 1)^{S} \times 2^{E ? 127} \times (1 + N)

其中各項(xiàng)的取值范圍：

\begin{matrix} S \in & {0, 1}, E \in {1, 2, \dots, 254} \\ (1 + N) = & (1 + \sum_{i = 1}^{23} b_{23 ? i} 2^{? i}) ? [1, 2 ? 2^{? 23}] \end{matrix}

IEEE 754 標(biāo)準(zhǔn)下的 float 的計(jì)算示例

圖 3-5 IEEE 754 標(biāo)準(zhǔn)下的 float 的計(jì)算示例

觀察圖 3-5 ，給定一個(gè)示例數(shù)據(jù) S=0 ， E=124 ，N= 2^(?2)+2^(?3)=0.375 ，則有：

val = (? 1)^{0} \times 2^{124 ? 127} \times (1 + 0.375) = 0.171875

現(xiàn)在我們可以回答最初的問題：float 的表示方式包含指數(shù)位，導(dǎo)致其取值范圍遠(yuǎn)大于 int 。根據(jù)以上計(jì)算，float 可表示的最大正數(shù)為 2^(254?127)×(2?2^(?23))≈3.4×10^38 ，切換符號(hào)位便可得到最小負(fù)數(shù)。

盡管浮點(diǎn)數(shù) float 擴(kuò)展了取值范圍，但其副作用是犧牲了精度。整數(shù)類型 int 將全部 32 位用于表示數(shù)字，數(shù)字是均勻分布的；而由于指數(shù)位的存在，浮點(diǎn)數(shù) float 的數(shù)值越大，相鄰兩個(gè)數(shù)字之間的差值就會(huì)趨向越大。

如表 3-2 所示，指數(shù)位 E=0 和 E=255 具有特殊含義，用于表示零、無窮大、NaN 等。

表 3-2 指數(shù)位含義

指數(shù)位 E	分?jǐn)?shù)位 $N = 0$	分?jǐn)?shù)位 $N \neq 0$	計(jì)算公式
$0$	$\pm 0$	次正規(guī)數(shù)	$(? 1)^{S} \times 2^{? 126} \times (0. N)$
$1, 2, \dots, 254$	正規(guī)數(shù)	正規(guī)數(shù)	$(? 1)^{S} \times 2^{(E ? 127)} \times (1. N)$
$255$	$\pm \infty$	$NaN$

值得說明的是，次正規(guī)數(shù)顯著提升了浮點(diǎn)數(shù)的精度。最小正正規(guī)數(shù)為 2^(?126) ，最小正次正規(guī)數(shù)為 2^(?126)×2^(?23) 。

雙精度 double 也采用類似 float 的表示方法，在此不做贅述。

以上內(nèi)容是否對(duì)您有幫助：

← C++基本數(shù)據(jù)類型

C++字符編碼 →

寫筆記

我要補(bǔ)充