本章我們來(lái)研究三種重要的數(shù)字表示
-
無(wú)符號(hào)是基于傳統(tǒng)二進(jìn)制表示法参咙，表示大于或等于0的數(shù)字 -
補(bǔ)碼是表示有符號(hào)整數(shù)的最常見方式惕蹄，有符號(hào)整數(shù)可以是正或者為負(fù) -
浮點(diǎn)數(shù)是表示實(shí)數(shù)的科學(xué)計(jì)數(shù)法的以2為基數(shù)的版本
計(jì)算機(jī)的表示法是用有限的數(shù)量的位表示的數(shù)字編碼崇摄，所以，結(jié)果太大的時(shí)候吨娜，某些運(yùn)算就會(huì)
溢出巷折。浮點(diǎn)運(yùn)算溢出會(huì)產(chǎn)生特殊的值+∞，但是一組正數(shù)的乘積總是正的惧所，這點(diǎn)和整數(shù)不同骤坐。但是由于表示的精度有限，浮點(diǎn)運(yùn)算是不可結(jié)合的下愈。整數(shù)的表示雖然只能編碼一個(gè)相對(duì)較小的數(shù)值范圍纽绍，但是這種表示是精確的，而浮點(diǎn)數(shù)可以編碼一個(gè)較大的數(shù)值范圍势似，但是這種表示只是近似的拌夏。
2.1信息存儲(chǔ)
大多數(shù)計(jì)算機(jī)使用8位的塊，或者說(shuō)字節(jié)履因，作為最小的可尋址的內(nèi)存單位障簿，而不是訪問(wèn)內(nèi)存中單獨(dú)的位。機(jī)器級(jí)程序?qū)?nèi)存視為一個(gè)非常大的字節(jié)數(shù)組栅迄，稱為虛擬內(nèi)存站故。內(nèi)存的每個(gè)字節(jié)都由一個(gè)唯一的數(shù)字標(biāo)識(shí)，稱為它的地址毅舆，所有可能地址的集合稱為虛擬地址空間西篓。
十六進(jìn)制表示法
一個(gè)字節(jié)由8位組成，在二進(jìn)制表示法中朗兵，它的值域是0000000011111111污淋，用十六進(jìn)制書寫顶滩，它的值域是0x000xFF余掖。
以0x或者0X開頭的數(shù)字常量被認(rèn)為是16進(jìn)制，字符“A”~“F”既可以是大寫也可以是小寫礁鲁。
字?jǐn)?shù)據(jù)大小
字長(zhǎng)決定的最重要的系統(tǒng)參數(shù)就是虛擬地址空間的最大大小盐欺。對(duì)于一個(gè)字長(zhǎng)為ω位的機(jī)器而言，虛擬地址的范圍就是0 ~ 2^ω - 1仅醇，程序最多訪問(wèn)2^ω個(gè)字節(jié)冗美。
大部分?jǐn)?shù)據(jù)類型都編碼為有符號(hào)數(shù)值，除非有前綴關(guān)鍵字unsigned或者對(duì)確定大小的數(shù)據(jù)類型使用了特定的無(wú)符號(hào)聲明析二。（數(shù)據(jù)類型char是個(gè)例外）
尋址和字節(jié)順序
多字節(jié)對(duì)象被存儲(chǔ)為連續(xù)的字節(jié)序列粉洼，對(duì)象的地址為所用字節(jié)最小的地址节预。
最低有效字節(jié)在最前面的方式，稱為小端法属韧。
最高有效字節(jié)在最前面的方式安拟，稱為大端法。
許多比較新的微處理器是雙端法宵喂，然而實(shí)際上糠赦，一旦選擇了特定的操作系統(tǒng)，字節(jié)順序也就被固定下來(lái)锅棕。Android和iOS都是運(yùn)行于小端模式拙泽。
表示代碼
指令編碼是不同的，不同的機(jī)器類型使用不同的且不兼容的指令和編碼方式裸燎。
從機(jī)器的角度來(lái)看顾瞻，程序僅僅只是字節(jié)序列。
有關(guān)布爾代數(shù)
布爾運(yùn)算~對(duì)應(yīng)邏輯運(yùn)算NOT德绿，對(duì)應(yīng)集合的補(bǔ)朋其；
布爾運(yùn)算&對(duì)應(yīng)邏輯運(yùn)算AND，對(duì)應(yīng)集合的并脆炎；
布爾運(yùn)算|對(duì)應(yīng)邏輯運(yùn)算OR梅猿，對(duì)應(yīng)集合的交；
布爾運(yùn)算^對(duì)應(yīng)邏輯運(yùn)算亦或秒裕。
布爾運(yùn)算的分配率：a & (b | c) = (a & b)|(a & c),a | (b & c) = (a | b)&(a | c)
另外袱蚓，對(duì)于a ^ a = 0，因此還有(a ^ b) ^ a = b
這里有一些有意思的關(guān)于位運(yùn)算的東西几蜻，簡(jiǎn)單整理在一起喇潘，以后單開一個(gè)筆記，把一些位運(yùn)算的算法題歸類一下梭稚。
a ^= b;
b ^= a;
a ^= b;
這樣可以交換a和b的值颖低，但是這個(gè)種交換方式?jīng)]有性能上的優(yōu)勢(shì)，它僅僅是一個(gè)智力游戲（至少書上是這么說(shuō)的……）
有關(guān)邏輯運(yùn)算
C語(yǔ)言還提供了一組邏輯運(yùn)算符||弧烤、&&忱屑、和！暇昂，分別對(duì)應(yīng)命題邏輯中的OR莺戒，AND和NOT運(yùn)算。
邏輯運(yùn)算具有短路性急波。即：第一個(gè)參數(shù)求值能確定表達(dá)結(jié)果从铲，那么就不會(huì)對(duì)第二個(gè)參數(shù)求值。
有關(guān)位移運(yùn)算
C語(yǔ)言提供了位移運(yùn)算澄暮，向左或者向右移動(dòng)位模式名段。
C表達(dá)式x << k會(huì)x向左移動(dòng)k位阱扬，丟棄最高的k位，并在右端補(bǔ)k個(gè)0.
有一個(gè)相應(yīng)的友誼運(yùn)算x >> k伸辟。一般而言价认，機(jī)器支持兩種形式的右移：邏輯右移和算術(shù)右移。邏輯右移在左端補(bǔ)k個(gè)0自娩，算數(shù)右移是在左端補(bǔ)k個(gè)最高有效位的值用踩。
對(duì)于無(wú)符號(hào)數(shù)，右移必須是邏輯的忙迁。
Java表達(dá)式中脐彩，x >> k是算術(shù)右移，x >>> k是邏輯右移姊扔。
加減法優(yōu)先級(jí)比位移優(yōu)先級(jí)要高
一些位運(yùn)算的常見技巧
0 ^ a = a
a ^ a = 0
a & （a - 1）可以消除最右邊的一個(gè)1
位運(yùn)算x & 0xFF生成一個(gè)由x的最低有效字節(jié)組成的值惠奸，而其他字節(jié)就被置為0。
Java是用的補(bǔ)碼恰梢，0x7fffffff是最大正整數(shù)佛南，0x80000000是最小的負(fù)數(shù)。
和0x7fffffff按位與就是取絕對(duì)值了嵌言，然后那個(gè)按位或就是求負(fù)數(shù)嗅回。
可以用if ((a & 1) == 0)代替if (a % 2 == 0)來(lái)判斷a的奇偶性。
修改正負(fù)號(hào)就是按位取反再加一摧茴，也就是~x + 1
檢驗(yàn)補(bǔ)碼乘法是否溢出：
int p = x * y;
return !x || p / x == y;
2.2整數(shù)表示
整型數(shù)據(jù)類型表示有限范圍的整數(shù)绵载。
有一個(gè)很值得注意的特點(diǎn)是取值范圍是不對(duì)稱的，負(fù)數(shù)的范圍比正數(shù)的范圍大1.
無(wú)符號(hào)數(shù)的編碼
無(wú)符號(hào)數(shù)編碼詳見思維導(dǎo)圖苛白。
補(bǔ)碼編碼
補(bǔ)碼編碼詳見思維導(dǎo)圖娃豹。
ω位補(bǔ)碼所能表示的值的范圍：最小是位向量[10……0]，最大的值是位向量[01……1]购裙。
注意：-1和UMax有同樣的位表示——全1的串懂版。數(shù)值0在兩種表示方式中都是全0的串。
有符號(hào)數(shù)和無(wú)符號(hào)數(shù)之間的轉(zhuǎn)換
C語(yǔ)言允許在各種不同的數(shù)字?jǐn)?shù)據(jù)類型之間做強(qiáng)制轉(zhuǎn)換躏率。
強(qiáng)制類型轉(zhuǎn)換的結(jié)果保持位值不變躯畴，只是改變了解釋這些位的方式。
補(bǔ)碼轉(zhuǎn)無(wú)符號(hào)數(shù)詳見思維導(dǎo)圖禾锤。
無(wú)符號(hào)數(shù)轉(zhuǎn)為補(bǔ)碼詳見思維導(dǎo)圖私股。
執(zhí)行一個(gè)運(yùn)算的時(shí)候摹察，如果它的一個(gè)運(yùn)算數(shù)是有符號(hào)的而另一個(gè)是無(wú)符號(hào)的恩掷，那么C語(yǔ)言會(huì)隱式的將有符號(hào)數(shù)強(qiáng)制類型轉(zhuǎn)換為無(wú)符號(hào)數(shù)，并假設(shè)兩個(gè)數(shù)都是非負(fù)的供嚎，來(lái)執(zhí)行運(yùn)算黄娘。
擴(kuò)展一個(gè)數(shù)字的位表示
要將一個(gè)無(wú)符號(hào)數(shù)轉(zhuǎn)換為一個(gè)更大的數(shù)據(jù)類型峭状，只需要簡(jiǎn)單的在表示的開頭添加0，這種運(yùn)算被稱為零擴(kuò)展逼争。
要將一個(gè)補(bǔ)碼數(shù)字轉(zhuǎn)換為一個(gè)更大的數(shù)據(jù)類型优床，可以執(zhí)行一個(gè)符號(hào)擴(kuò)展，在表示中添加最高有效位的值誓焦。
一個(gè)有意思的地方：
當(dāng)把short轉(zhuǎn)換成unsigned時(shí)胆敞，我們要先改變大小，之后再完成從有符號(hào)到無(wú)符號(hào)的轉(zhuǎn)換杂伟。也就是說(shuō)(unsigned)sx等價(jià)于(unsigned)(int)sx
截?cái)鄶?shù)字
將一個(gè)ω位的數(shù)字截?cái)酁橐粋€(gè)k位的數(shù)字移层，我們會(huì)丟棄最高的ω - k位。
補(bǔ)碼截?cái)嘁灿邢嗨频膶傩院罩啵贿^(guò)要將最高位轉(zhuǎn)換為符號(hào)位观话，也就是說(shuō)，一個(gè)正數(shù)截?cái)嗔艘院罂赡芫妥兂闪素?fù)數(shù)越平。
2.3整數(shù)運(yùn)算
無(wú)符號(hào)加法
詳見思維導(dǎo)圖
如果s沒(méi)有溢出频蛔，則可以肯定s ≥ x
無(wú)符號(hào)數(shù)求反詳見思維導(dǎo)圖
補(bǔ)碼加法
詳見思維導(dǎo)圖
對(duì)滿足TMinω ≤ x， y ≤ TMaxω 的x和y秦叛，另s = x + y晦溪，當(dāng)且僅當(dāng)x > 0，y > 0挣跋，但s ≤ 0時(shí)尼变，計(jì)算s發(fā)生了正溢出。當(dāng)且僅當(dāng)x < 0浆劲，y < 0嫌术，但s ≥ 0時(shí)，計(jì)算s發(fā)生了負(fù)溢出牌借。
補(bǔ)碼的非
詳見思維導(dǎo)圖
無(wú)符號(hào)乘法
詳見思維導(dǎo)圖
補(bǔ)碼乘法
詳見思維導(dǎo)圖
乘以常數(shù)
編譯器使用了一項(xiàng)重要優(yōu)化度气，試著用位移和加法運(yùn)算的組合來(lái)代替乘以常數(shù)因子的乘法。
考慮一組從位位置n到位位置m的連續(xù)的1（n≥m）我們可以用下面兩種不同形式中的一種來(lái)計(jì)算這些位對(duì)乘積的影響：
- 形式A：(x << n) + (x << n - 1) + ... + (x << m)
- 形式B：(x << (n + 1)) - (x << m)
除以2的冪
- 除以2的冪無(wú)符號(hào)除法：C變量x和k有無(wú)符號(hào)數(shù)值x和k膨报，且0 ≤ k ＜ ω磷籍，則x>>k產(chǎn)生數(shù)值，x / 2^k
- 除以2的冪補(bǔ)碼除法现柠，向下舍入：C變量補(bǔ)碼x和無(wú)符號(hào)k院领，且0 ≤ k ＜ ω，當(dāng)執(zhí)行算術(shù)位移時(shí)够吩，x>>k產(chǎn)生數(shù)值x / 2^k
- 除以2的冪的補(bǔ)碼除法比然，向上舍入：C變量補(bǔ)碼x和無(wú)符號(hào)k，且0 ≤ k ＜ ω周循，當(dāng)執(zhí)行算術(shù)位移時(shí)强法，（x + (1 << k）- 1) >> k產(chǎn)生數(shù)值x / 2^k万俗。
遺憾的是，和乘法不同饮怯，我們不能用除以2的冪的出發(fā)來(lái)表示任意常數(shù)K的除法闰歪，所以除法絕大多數(shù)情況下指令會(huì)相當(dāng)慢。
2.4浮點(diǎn)數(shù)
二進(jìn)制小數(shù)
定義見思維導(dǎo)圖
IEEE浮點(diǎn)表示
IEEE浮點(diǎn)標(biāo)準(zhǔn)用V = (-1)^s * M * 2^E
- s：sign蓖墅，符號(hào)库倘，決定正負(fù)。
- M：significand论矾，尾數(shù)于樟，通常是[1.0~2.0)范圍的小數(shù)
- E：exponent，階碼拇囊，就是次方數(shù)迂曲。
單精度浮點(diǎn)格式中，s寥袭，exp和frac字段分別為1位路捧、k = 8位和n = 23位，得到一個(gè)32位的表示传黄。雙精度浮點(diǎn)格式中杰扫，s、exp和frac字段分別為1位膘掰、k = 11位和n = 52位章姓，得到一個(gè)64位的表示。
規(guī)格化的值
解碼字段被解釋為偏置形式表示的有符號(hào)整數(shù)识埋。階碼的值是E = e - Bias凡伊，其中e是無(wú)符號(hào)數(shù)，而Bias是一個(gè)等于2^(k-1) - 1的偏置值窒舟。
小數(shù)子段frac被解釋為描述小數(shù)值f系忙，其中0 ≤ f < 1，二進(jìn)制小數(shù)在最高有效為的左邊惠豺。尾數(shù)定義為M = 1 + f银还。這種方式也叫做隱含的以1開頭的表示.
非規(guī)格化的值
階碼值是E = 1 - Bias，而尾數(shù)的值是M = f洁墙，也就是小數(shù)字段的值蛹疯，不包含隱含的開頭的1.
非規(guī)格化數(shù)的另外一個(gè)功能是表示那些非常接近于0.0的數(shù)。它們提供了一種屬性热监，稱為逐漸溢出捺弦，其中，可能的數(shù)值分布均勻的接近于0.0.
特殊值
最后一類數(shù)值是當(dāng)階碼全為1的時(shí)候出現(xiàn)的。當(dāng)小數(shù)域全為0時(shí)羹呵，得到的值表示無(wú)窮骂际，當(dāng)s = 0時(shí)是+∞疗琉，當(dāng)s = 1時(shí)是-∞冈欢。當(dāng)我們把兩個(gè)非常大的數(shù)相乘，或者除以零時(shí)盈简，無(wú)窮能夠表示溢出的結(jié)果凑耻。當(dāng)小數(shù)域?yàn)榉橇愕臅r(shí)候，結(jié)果值被稱為“NaN”柠贤，即“不是一個(gè)數(shù)（Not a Number）”的縮寫香浩。一些運(yùn)算的結(jié)果不能是實(shí)數(shù)或無(wú)窮，就會(huì)返回這樣的NaN值臼勉，比如當(dāng)計(jì)算根號(hào)-1或者∞-∞時(shí)邻吭。
浮點(diǎn)數(shù)的一些Point
- 值+0.0總有一個(gè)全為0的位表示。
- 最小的正非規(guī)格化的位表示宴霸，是有最低有效位為1而其他所有位為0構(gòu)成的囱晴。它的數(shù)字值是V = 2(-n-2(k-1)+2)。
- 最大的非規(guī)格化值的位模式是由全為0的解碼字段和全為1的小叔子段組成的瓢谢。數(shù)值V = (1 - 2^(-n)) * 2((-2)(k-1)+2)畸写。
- 最小的正規(guī)格化值的位模式的階碼字段的最低有效位為1，其他位全為0氓扛。它的尾數(shù)值M = 1枯芬，而階碼值E = -2^(k-1) + 2。因此數(shù)值V = 2((-2)(k-1) + 2)采郎。
- 值1.0的位表示的階碼字段除了最高有效為等于1以外千所，其他位都等于0。它的尾數(shù)值是M = 1蒜埋，他的階碼值是E = 0.
- 最大的規(guī)格化值的位表示的符號(hào)位為0真慢，階碼的最低有效位等于0，其他位等于1.數(shù)值V = （1 - 2^(-n-1)） * 22(k-1)
舍入
IEEE浮點(diǎn)格式定義了四種不同的舍入方式理茎。默認(rèn)的方法是找到最接近的匹配黑界，其他三種可用于計(jì)算上界和下界。
浮點(diǎn)運(yùn)算
IEEE標(biāo)準(zhǔn)定義了一些使之更合理的規(guī)則皂林。例如朗鸠，定義1 / -0將產(chǎn)生-∞,而定義1 / +0會(huì)產(chǎn)生+∞
對(duì)于所有的x和y的值，實(shí)數(shù)的加法運(yùn)算是可交換的础倍。但是運(yùn)算是不可結(jié)合的烛占。例如（3.14 + 1e10）- 1e10
無(wú)窮（因?yàn)?∞ - ∞ = NaN）和 NaN是例外情況，因?yàn)閷?duì)于任何x都有NaN + x = NaN。
浮點(diǎn)加法滿足了單調(diào)性屬性：如果a ≥ b忆家，那么對(duì)任何a犹菇、b以及x的值，除了NaN芽卿，都有x + a ≥ x + b揭芍。
浮點(diǎn)乘法也遵循通常乘法所具有的許多屬性。它是可交換的卸例，不具有可結(jié)合行称杨。例如（1e20 * 1e20） * 1e-20位+∞，而1e20 * （1e20 * 1e-20）得出1e20筷转。
浮點(diǎn)乘法滿足單調(diào)性：
a ≥ b 且 c ≥ 0 → a * c ≥ b * c
a ≥ b 且 c ≤ 0 → a * c ≤ b * c
我們還可以保證姑原，只要a ≠ NaN，就有a * a ≥ 0.
C語(yǔ)言中的浮點(diǎn)數(shù)
所有C語(yǔ)言版本提供了兩種不同的浮點(diǎn)數(shù)據(jù)類型：float 和 double呜舒。
一些會(huì)產(chǎn)生錯(cuò)誤的點(diǎn)：
- 從int轉(zhuǎn)成float锭汛，數(shù)字不會(huì)溢出，但是可能被舍入袭蝗。
- 從int或float轉(zhuǎn)成double唤殴，因?yàn)閐ouble有更大的范圍，也有更高的精度呻袭，所以能夠保留精確的數(shù)值眨八。
- 從double轉(zhuǎn)換成float，因?yàn)榉秶∽蟮纾灾悼赡芤绯龀?∞或者-∞廉侧，另外，也可能舍入篓足。
- 從float或double轉(zhuǎn)成int段誊，值將會(huì)向零舍入。例如1.999轉(zhuǎn)換為1栈拖，而-1.999轉(zhuǎn)為-1.進(jìn)一步來(lái)說(shuō)连舍，值可能會(huì)溢出。與Inter兼容的微處理器指定位模式[10...00]（字長(zhǎng)為ω時(shí)的TMinω）為
整數(shù)不確定值涩哟。一個(gè)從浮點(diǎn)數(shù)到整數(shù)的轉(zhuǎn)換索赏，如果不能為該浮點(diǎn)數(shù)找到一個(gè)合理的整數(shù)近似值，就會(huì)產(chǎn)生一個(gè)這樣的值贴彼。因此潜腻，表達(dá)式（int）+le10會(huì)得到-21483648，即從一個(gè)正值變成了一個(gè)負(fù)值Ｆ髡獭Ｈ诨痢童番！
課后題中的一些點(diǎn)
- 表達(dá)式~0xFF創(chuàng)建一個(gè)掩碼，該掩碼8個(gè)最低位為0威鹿，其余的為1.這個(gè)掩碼的產(chǎn)生與字長(zhǎng)無(wú)關(guān)剃斧。相比之下，0xFFFFFF00只能工作在32位機(jī)器上忽你。
- x ^ y = (x & ~y) | (~x & y)
- TMin32是-2147483648幼东，并且將它強(qiáng)制類型轉(zhuǎn)換為無(wú)符號(hào)數(shù)后，變成了2147483648檀夹。另外筋粗，如果有任何一個(gè)運(yùn)算數(shù)是無(wú)符號(hào)的策橘，那么在比較之前炸渡，另一個(gè)運(yùn)算數(shù)會(huì)被強(qiáng)制類型轉(zhuǎn)換為無(wú)符號(hào)數(shù)。
- 函數(shù)的任何測(cè)試過(guò)程中丽已，TMin 都應(yīng)該作為一種測(cè)試情況０龆隆！沛婴！
- 對(duì)于無(wú)符號(hào)數(shù)的非吼畏，位的模式是相同的。
- int64_t pll = (int64_t) x * y;這一句如果寫成int64_t pll = x * y;就會(huì)用32位的值來(lái)計(jì)算乘積（這時(shí)候可能就溢出了嘁灯！）泻蚊，然而再符號(hào)擴(kuò)展到64位。
- 表達(dá)式x>>32產(chǎn)生一個(gè)字丑婿，如果x是負(fù)數(shù)性雄，這個(gè)字全為1，否則全為0.這個(gè)訣竅偶爾會(huì)有大用處羹奉。
- 一個(gè)具有n位小數(shù)的浮點(diǎn)格式秒旋，不能準(zhǔn)確描述的最小正整數(shù)是：1后面跟著n個(gè)0后面再跟一個(gè)1.即2^(n+1) + 1
- 2.44C的謎題里的需要理解的計(jì)算機(jī)運(yùn)算的屬性。
32位機(jī)器诀拭，有符號(hào)值使用算術(shù)右移迁筛，無(wú)符號(hào)值使用邏輯右移
int x,y
unsigned ux,uy
A. (x > 0）||((x - 1) < 0
False 假設(shè)x = TMin32，那么x - 1 = TMax32
B. (x & 7) != 7 || (x << 29 < 0)
True
C. (x * x) >= 0
False 當(dāng)x為0xFFFF時(shí)耕挨，x * x為-131071（0xFFFE0001）
D. x < 0 || -x <= 0
True
E. x > 0 || -x >= 0
False 設(shè)x = TMin32（好吧细卧，又是它）那么x和-x都是負(fù)數(shù)！
F. x + y == uy + ux
True
G. x * ~y + uy * ux == -x
True ~y等于-y-1.uy * ux等于x * y筒占，所以左邊等價(jià)于x * -y - x + x * y贪庙。
勘誤：43頁(yè)第一段原文中寫的是復(fù)數(shù)的范圍比整數(shù)的范圍大1，應(yīng)該是正數(shù)……
