CS:APP

第二章 信息的表示與處理

十六進制與二進制轉換

0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0000 0001 0010 0011 0100 0101 0110 0111
8 9 A B C D E F
8 9 10 11 12 13 14 15
1000 1001 1010 1011 1100 1101 1110 1111

尋址和字節順序

有效位

(最高有效位1)123456789(最低有效位9)

大端 01 23 45 67
小端 67 45 23 01
指針與樹組
1
start[i] == *(start + i) //auto dereference
布爾代數

異或(^): a或b其中一個為1，一個為0時成立，即返回1，否則返回0

~x = -x-1

位向量

位向量[01101001] (從右到左，由0開始，第n位表示(n-1)是否存在集合中)表示集合{0, 3, 5, 6}

C語言中的位級運算

對十六進制位運算 -> 轉二進制 ->運算完再轉十六進制

整數表示

C語言中的移位運算

邏輯右移(無符號): x>>k會在左端補k個0

算術右移(有符號):x>>k會在左端補k個最高位的值

若移動(左移或右移)k位，且k > w(w位數據)，則移動k mod w位

若想形成w-k個零後跟著k個1的位向量，可由(1<<k) - 1生成 (用於掩碼運算)

ex: (1<<8) - 1 => 0xFF

無符號數的編碼

對向量x = [Xw-1, Xw-2, …, X0]:

補碼編碼

對向量x = [Xw-1, Xw-2, …, X0]:

有符號數與無符號數的轉換
拓展數的位表示
無符號: 零拓展

開頭補零

有符號: 符號拓展

開頭補最高有效位

截斷數字

對位向量取模2^k表示保留數字的低k位，高於k位的部分被截去

截斷無符號數: x’ = x mod 2^k
截斷有符號數: (T)[(U)x mod 2^k]

整數運算

無符號加法
判斷加法中的溢出
無符號數求反

補碼加法會形成阿貝爾群，所以無論有沒有溢出(x+y)-x總會等於y

此處x, y視為有符號數

檢測補碼加法中的溢出
補碼的非
補碼非的位級表示
  • -x = (~x) + 1 即補碼非 = 求補後+1
  • 補碼非 = 從右向左數第一個1左邊的所有位取反
無符號乘法
補碼乘法
乘以常數

對於某個常數K的表達式x*K生成代碼

將K表達成一組0與1交替的序列

例如: 14可寫成[(0…0)(111)(0)]。

考慮一組從位置n到位置m的連續的1(n >= m)(對14來說: n = 3 m = 1)

(法1) (x<<n)+(x<<(n-1))+…+(x<<m)

(法2) (x<<(n+1))-(x<<m)

(注: 2^{n+1} - 2^m = (2^n + 2^{n-1} + … + 2^m))

把每個連續的1的結果加起來即x*K

除以2的幂

除以2的幂的無符號除法(邏輯右移): x>>k等於(x/2^k，向下捨入)

除以2的幂的補碼除法(算數右移): (x<0 ? x+(1<> k

x > 0:

  • x>>k (向下捨入)

x < 0:

  • (x+(1<>k (加入偏移，向上捨入)
    • 利用特性(x/y，向上捨入) = ((x+y-1)/y，向下捨入)

浮點數

二進制小數

由上式可推: 二進制小數點向左移動一位相當於該數被2除，向右移動一位相當於該數乘2

IEEE浮點表示

注：若溢出，則表示為正/負無窮

  • 符號(sign): s決定正(s=0)負(s=1)
  • 階碼(exponent): E對浮點數加權，權重為2的E次幂(E可<0)
  • 尾數(significand): M為二進制小數，範圍在1<=M<2，或0<=M<1

浮點數的位表示分為三個字段:

  • 符號位s，編碼符號s
  • k位的編碼字段exp，編碼階碼E
  • n位的小數字段frac，編碼尾數M，編碼出來的值依賴於階碼字段的值是否為零

float: s = 1, k = 8, n = 23

double: s = 1, k = 11, n = 52

根據exp的值，分:

  1. 規格化的值

    exp位不全為0(0)或全為1(255)時屬之，階碼字段(E)為以偏置形式表示的有符號整數

    E = e - Bias，其中，e為無符號數(exp的值)，Bias為2^{k-1}-1(float: 127, double: 1023)

    故，E取值範圍: float: -126~+127，double: -1022~+1023

    frac被解釋為小數值f，其中0<=f<1，其二進制表示為0.fn-1…f1f0。M=1 + f (implied leading 1)

  2. 非規格化的值

    exp位全為0時屬之，階碼E = 1 - Bias，尾數M = f，不包含隱含的開頭1

    用途: 1.表示0 2.表示非常接近0.0的數

  3. 特殊值

    exp位全為1時屬之，當frac全為0時表示無窮。s=1表示負無窮，s=0表示正無窮

    當二非常大的數相乘，或除以零時，無窮可以表示溢出的結果。

    當frac為非零時，即”NaN (Not a number)”，比如sqrt(-1)或無窮-無窮，亦可表示位初始化數據

整數轉浮點
  1. 將數字表示成二進制
  2. 將此二進制表示成二進制小數 * 2^E
  3. 丟棄開頭的1(後期轉M時會自動+1)，填充0以構造小數字段
  4. 構造階碼字段，用E+bias算e後轉為二進制
  5. 加上符號位
捨入

  • 向偶捨入(默認): 嘗試尋找最接近的匹配值，如果是兩個可能結果的中間值，則捨入到最低有效數字為偶數者

  • 向零捨入: 正數向下捨入，負數向上捨入，使得|x’| <= |x|

  • 向下捨入: x’ <= x
  • 向上捨入: x <= x’
浮點運算
  • 1/+0 = 正無窮
  • 1/-0 = 負無窮

定義x+^fy=Round(x + y)

  • x+^fy = y+^fx
  • 不符結合律
    • (3.14+1e10) - 1e10 != 3.14 + (1e10-1e10)
  • NaN +^f x = NaN
  • a >= b => x + a >= x + b (整數或補碼加法不符合)

定義x^fy=Round(x y)

  • 不符結合，分配律
  • a != NaN => a *^f a >= 0
C語言中的浮點數
  • int轉float，數字不會溢出，但可能被捨入
  • int/float轉double，因為double範圍較大，保留精確數值
  • double轉float，可能溢出成正/負無窮或被捨入
  • float/double轉int，向零捨入，可能溢出

練習題

2.5

A 小端法 21 大端法 87

B 小端法 21 43 大端法 87 65

C 小端法 21 43 65 大端法 87 65 43

2.6

A(a) 00000000001101011001000101000001

A(b) 00111010010101100100010100000100

B 承上

C 略

2.7

61 62 63 64 65 66 00 (strlen(s)不計算中止的空字符: 即00)

2.8

~a 10010110

~b 10101010

a&b 01000001 (0 & 0 ==> 0)

a | b 01111101

a ^ b 00111100

2.9

A

[1,1,1]

[1,1,0]

[1,0,1]

[1,0,0]

[0,1,1]

[0,1,0]

[0,0,1]

[0,0,0]

B

[0,1,1]

[0,1,0]

[0,0,1]

2.10

1 x = a y = a^b

2 x = a^(a^b) = b y = a^b

3 x = b y = b^(a^b) = a

2.11

A first = last = k

B

1 x = a y = a^a = 0

2 x = 0^0=0 y = 0

3 x = 0 y = 0^0=0

C first <= last修改為first < last

2.12

A x&0xFF

B ~(x^0xFF)

C x | 0xFF

2.13

OR: bis(x,y)

XOR: bis(bic(x,y), bic(x,y))

a ^ b = (a & ~b) | (~a & b)

a & ~b ==> a為1且b為0，返回1，否則為0

~a & b ==> a為0且b為1，返回1，否則為0

2.14

x = 0x66 y = 0x39 ==>

x = 01100110 ~x = 10011001(0x99)

y = 00111001 ~y = 11000110(0xC6) !y = 00000001 = 0x01 = 0x00

表達式 值 表達式 值
x & y 00100000(0x20) x && y 0x01
x \ y 01111111(0x7F) x \ \ y 0x01
~x \ ~y 11011111(0xDF) !x \ \ !y 0x00
x & !y 00000000(0x00) x && ~y 0x01
2.15

!(x^y)

因為僅x = y時，x^y = 0

2.16

  1. x << 3

  2. x>>2(邏輯)

  3. x>>2(算數)

hex bin bin hex bin hex bin hex
0xC3 11000011 00011000 0x18 00110000 0x30 11110000 0xF0
0x75 01110101 10101000 0xA8 00011101 0x1D 00011101 0x1D
0x87 10000111 00111000 0x38 00100001 0x21 11100001 0xE1
0x66 01100110 00110000 0x30 00011001 0x19 00011001 0x19
2.17
hex bin B2U B2T
0x0 0000 0 0
0x5 0101 5 5
0x8 1000 8 -8
0xD 1101 13 -3
0xF 1111 15 -1
2.18

略

2.19
x T2U(x)
-8 8
-3 13
-2 14
-1 15
0 0
5 5
2.20

略

2.21

不想做

2.22

略

2.23

A

w fun1(w) fun2(w)
0x00000076 0x00000076 0x00000076
0x87654321 0x00000021 0x00000021
0x000000C9 0x000000C9 0xFFFFFFC9
0xEDCBA987 0x00000087 0xFFFFFF87

B

保留後兩位，若倒數第二位>=8，則變號

fun1: 取低八位，得到0~255的整數

fun2: 取低八位，並進行符號拓展，得到-128~127的整數

2.24

4位 -> 3位

(1)無符號

(2)補碼

原始值 截斷值 原始值 截斷值
0 0 0 0
2 2 2 2
9 1 -7(1001) => 9(U) 1
11 3 -5(1011) => 11(U) 3
15 7 -1(1111) => 15(U) 7 -1

​ *注: 15(U)需mod 2^k = 7(U) => 7-2^3 = -1(T)

2.25

當length = 0時，(int) length = -1 = (unsigned) (-1 + 2^32) > 0，訪問超出數組長度，返回內存錯誤

修改unsigned length成int length

2.26

A strlen(s) < str(t)時

B size_t 嘗試 < 0 ，造成得到size_t + 2^32的值，故此函數總是返回1

C轉儲strlen(s)與strlen(t)在二int中，返回此二int相減>0

2.27
1
2
3
4
5
/* Determin whether arguments can be added without overflow */
int uadd_ok(unsigned x, unsigned y){
    unsigned tmp = x + y;
    return tmp >= x;
}
2.28

w = 4

(1) x

(2) -^u_w x補碼加法

hex dec dec hex
0 0 0 0
5 5 11 AB
8 8 8 8
D 1413 23 23
F 15 1 1
2.29

略

2.30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* Determin whether arguments can be added withou overflow */
int tadd_ok(int x, int y)
{
    int tmp = x + y;
    // Be careful: is "<=" not "<" 
    if ((x > 0) && (y > 0) && tmp <= 0)
    {
        return 0;
    }
    else if ((x < 0) && (y < 0) && tmp >= 0)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
2.31

補碼加會形成阿貝爾群，所以(x+y)-x無論是否溢出都會=y

2.32

當y=TMin時，-y也等於TMin。題目中的函數會認為x<0時會溢出x>0時不會溢出。然而事實相反，x<0時不會溢出，x>0時才會溢出。

2.33

(1) x

(2) -^t_4 x

TMin_w = -8

hex dec dec hex
0 0 0 0
5 5 -5[1011] B
8 -8 -8 8
D[1101] -3 3 3
F[1111] -1 1 1
2.34

2^3 = 8

2^2 = 4

TMax = 3

模式 x y x * y 截斷的x * y
U [100]4 [101]5 20 4
T [100]-4 [101]-3 12 -4
U [010]2 [111]7 14 6
T [010]2 [111]-1 -2 -2
U [110]6 [110]6 36 4
T [110]-2 [110]-2 4 -4
2.35
2.36
1
2
3
4
5
6
7
8
9
10
/* Determine whether arguments can be multiplied without overflow */
int tmult_ok(int x, int y)
{
    /* Be careful: 
    *  not x * y
    *  since x * y will use (int) to calculate then sign extend to (int64_t), might cause overflow
    */
    int64_t tmp = (int64_t)x * y;
	return tmp == (int)tmp;
}
2.37

A 可存放數值擴大到2^63 - 1，但是執行malloc時會將其再次轉換為int，所以此改動沒有任何作用

B 分配內存前先運行2.36時創造的tmult_ok函數，確認後再分配

2.38

k=0 b=0: 1

k=0 b=a: 2

k=1 b=0: 2

k=1 b=a: 3

k=2 b=0: 4

k=2 b=a: 5

k=3 b=0: 8

k=3 b=0: 9

2.39

-(x<<m)，因為(x<<n+1) = 0

2.40
K 移位 加法/減法 表達式
6 2 1 (x<<3) - (x<<1)
31 1 1 (x<<5) - (x<<0)
-6 2 1 (x<<1) - (x<<3)
55 2 2 (x<<6) - (x<<3) - (x<<0)
2.41

B 當n = m: A, n = m+1: A/B, n > m+1: B

2.42

因為為32位，所以x>>31表示x>0得到全0，x<0得到全1

其中，若x<0，bias = 15(1111)

1
2
3
4
5
6
7
8
/* This training is super important since I have no idea about how to solve it at the begining. */
/* Calculate x/16 without: /, %, *, if, ?, :, <, >, == */
int div16(int x)
{
    int bias = (x>>31) & 0xF;
    
    return (x + bias) >> 4;
}
2.43

M = 31

N = 8

2.44

A 畫出一維數線可證 x = TMin, x-1 = TMax

B (x != 7 || x != 15) && x < (2^31-1)/2^29 若想x&7 != 7為0，則X2必為1，左移29位後，成為符號位(必<0)

7 = 0111

x & 7 = 7 => x=7 or 15

C x = 2^31-1 (mod2^32後剛好成1…) x = 2^30-1

D 由”補碼的非”的公式可證

E x = TMin

F x = -1, y = -1 ux = -1 + 2^32, uy = -1+2^32

2*2^32 -2 mod 2^32 = 0 -2(T)

標準解答: 補碼與無符號加法有相同的位級行為，而且它們是可交換得(注: 且進行==對比時，會將二者轉換成相同類型)

G x = 1, y = 1 ux = 1, uy = 1

因為~y = -y-1

所以原式=x-y-x+xy = -x

2.45

Tip: 先將分子轉乘二進制，然後小數點插入在從右算起的第(分母是2的多少次方)位

Ex: 25/16 -> 25 = 11001, 16 = 2^4 => 25/16 = 1.1001

小數值 二進制表示 十進制表示
1/8 0.001 0.125
3/4 0.11 0.75
25/16 1.1001 1.5625
43/16 10.1011 2.6875
9/8 1.001 1.125
47/8 101.111 5.875
51/16 11.0011 3.1875
2.46

略，感覺好麻煩

2.47
位 e E 2^E f M 2^E * M V dec
0 00 00 0 0 1 0 0 0 0 0
0 00 01 0 0 1 1/4 1/4 1/4 1/4 0.25
0 00 10 0 0 1 1/2 1/2 1/2 1/2 0.5
0 00 11 0 0 1 3/4 3/4 3/4 3/4 0.75
0 01 00 1 0 1 0 1 1 1 1
0 01 01 1 0 1 1/4 5/4 5/4 5/4 1.25
0 01 10 1 0 1 1/2 3/2 3/2 3/2 1.5
0 01 11 1 0 1 3/4 7/4 7/4 7/4 1.75
0 10 00 2 1 2 0 1 2 2 2
0 10 01 2 1 2 1/4 5/4 5/2 5/2 2.5
0 10 10 2 1 2 1/2 3/2 3 3 3
0 10 11 2 1 2 3/4 7/4 7/2 7/2 3.5
0 11 00 - - - - - - 正無窮 -
0 11 01 - - - - - - NaN -
0 11 10 - - - - - - NaN -
0 11 11 - - - - - - NaN -
2.48

(int)3510593 = 0x00359141

(float)3510593.0 = 0x4A564504

int = [00000000001101011001000101000001]

float = [01001010010101100100010100000100]

相關區域對應整數低位，在等於1的最高有效位之前停止，與浮點小數部分高位是相匹配的。

2.49

A 1 + 2^{n+1}

B 1 + 2^24

2.50

A 2+(1/4) => 3

B 2+(3/8) => 2+(1/2)

C 2+(3/4) => 3

D 3+(1/8) => 3

2.51

A x’ = 0.000110011001100110011001

B x’ - 0.1 = 0 0.1 * 2^(-22)

C 0.086s

D 171m

2.52

(用類似整數轉浮點的方式)

A A B B
位 值 位 值
011 0000 1 0111 000 1
101 1110 15/2 1001 111 15/2
010 1001 25/32 0110 100 3/4
110 1111 31/2 1011 000 16
000 0001 1/64 0001 000 1/64

111.1 = 1.111 * 2^2

0.11001 = 1.1001 * 2^(-1)

1111.1 = 1.1111 2^3 => 1.000 2^4

0.000001 = 0.001 2^(-3) = 1.000 2^(-6)

2.53
1
2
3
#define POS_INFINITY 1e400	//只要>1.8*10^308導致溢出即可
#define NEG_INFINITY -(POS_INFINITY)
#define NEG_ZERO (-1.0/POSINFINITY)
2.54

A 真，C語言中的浮點數，第2點說明

B 假，x=TMax

C 假，d=1e40，右側得到正無窮

D 真，第二點說明

E 假 真，浮點數取非僅僅對符號位取反

F 假 真，執行除法前，分子與分母都會傳換成浮點表示

G 真，浮點運算，最後一點說明

H 假，f=1e20，d=1，f+d捨入到1e20，左邊為0，右邊為1