版權(quán)聲明：本文為 gfson 原創(chuàng)文章，轉(zhuǎn)載請注明出處。
注：作者水平有限，文中如有不恰當(dāng)之處，請予以指正，萬分感謝。

2.55 - 2.57

2.55 - 2.57.png

答案：

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len){
    size_t i;
    for(i=0;i<len;i++)
        printf(" %.2x",start[i]);
    printf("\n");
}

void show_short(short x){
    show_bytes((byte_pointer) &x, sizeof(short));
}

void show_int(int x){
    show_bytes((byte_pointer) &x, sizeof(int));
}

void show_long(long x){
    show_bytes((byte_pointer) &x, sizeof(long));
}

void show_float(float x){
    show_bytes((byte_pointer) &x, sizeof(float));
}

void show_double(double x){
    show_bytes((byte_pointer) &x, sizeof(double));
}

int main(void){
    
    short s = 34;
    int i = 34;
    long l = 34L;
    float f = 34.0f;
    double d = 34.0;
    
    show_short(s);
    show_int(i);
    show_long(l);
    show_float(f);
    show_double(d);
    
    return 1;
}

上述代碼運(yùn)行后，結(jié)果如下：

result.png

可以直觀的看到當(dāng)前計算機(jī)上各個類型所占的字節(jié)。其中，short 占 2 個字節(jié)， int、long、float 占 4 個字節(jié)，double 占 8 個字節(jié)。
可以看出當(dāng)前機(jī)器字節(jié)順序使用的是小端法。
short、int、long 計算：2 * 16 + 2 = 34。
float 計算：

0x420800 = [0100 0010 0000 1000 0000 0000]₂
由于遵循 IEEE 標(biāo)準(zhǔn)，float 中 s 字段為 1，k = 8，n = 23，所以：
- Bias = 2^k-1 - 1 = 127，
  e = [1000 0100] ₂ = 132，
  E = e - Bias = 5，
  f = [0.000 1000 0000 0000 0000 0000]₂ = 1/16，
  M = 1 + f = 1 + 1/16，
  s = 0，
  V = （-1）^s * 2^E * M = 32 * （1 + 1/16） = 34。

double 計算：

0x4041000000000000 = [0100 0000 0100 0001 0000 0000 ... 0000]₂
由于遵循 IEEE 標(biāo)準(zhǔn)，double中 s 字段為 1，k = 11，n = 52，所以：
- Bias = 2^k-1 - 1 = 2¹⁰ - 1，
  e = [100 0000 0100] ₂ = 2¹⁰ + 4，
  E = e - Bias = 5，
  f = [0.000 1000 0000 0000 0000 0000 ... 0000]₂ = 1/16，
  M = 1 + f = 1 + 1/16，
  s = 0，
  V = （-1）^s * 2^E * M = 32 * （1 + 1/16） = 34。

2.58

2.58.png

答案：

int is_little_endian(){
    int a = 1;
    return *((char*)&a);
}

int main(void){ 
    int result = is_little_endian();
    printf("result is: %d \n",result);
    return 1;
}

2.59

2.59.png

答案：

int mix(int x, int y){
    return (x & 0xFF) | (y & (~0xFF));
}

int main(void){ 
    int result = mix(0x89AECDEA,0x76743210);
    printf("result is: %x \n",result);
    return 1;
}

2.60

2.60.png

答案（兩種方法）：

unsigned replace_byte_1(unsigned x, int i, unsigned char y){
    char* start = (char*)&x;
    start[i] = y;
    return x;
}

unsigned replace_byte_2(unsigned x, int i, unsigned char y){
    return (x & ~(0xFF<<(i<<3)) | (y << (i<<3)));
}

int main(void){ 
    unsigned result_1 = replace_byte_1(0x12345678, 2, 0xAB);
    printf("result_1 is: %x \n",result_1);
    unsigned result_2 = replace_byte_2(0x12345678, 3, 0xAB);
    printf("result_2 is: %x \n",result_2);
    return 1;
}

以參數(shù)（0x12345678, 2, 0xAB）為例，從 0x12345678 -> 0x12AB5678 需要經(jīng)歷如下過程：
1. 0xAB -> 0x00AB0000，0xAB << 2 * 2 *4，0xAB << 2 << 3，y << (i << 3)
2. 0x12345678 -> 0x12005678，0x12345678 & 0xFF00FFFFFF，0x12345678 & ~0x00FF000000，0x12345678 & ~(0xFF << 2 * 2 * 4)，0x12345678 & ~(0xFF << 2 << 3)，(x & ~ (0xFF << (i<<3))
3. 0x12AB5678 = 0x00AB0000 | 0x12005678 = (x & ~(0xFF << (i<<3)) | (y << (i<<3)))

位級整數(shù)編碼規(guī)則

位級整數(shù)編碼規(guī)則-1.png

位級整數(shù)編碼規(guī)則-2.png

2.61

2.61.png

答案：
- A: !(~x)
- B: !x
- C: !((~x) & 0xFF)
- D: !(x & (~0xFF)) 或者 !(x>>((sizeof(int)-1)<<3))

核心判斷是零與非零，目的是需要達(dá)到在一種情況下結(jié)果所有位為 0，其他情況下有些位不為 0。
在 D 中，可以通過 x & (~0xFF) 的方法使得除最高位字節(jié)以外的字節(jié)都為 0，也可以通過 (x>>((sizeof(int)-1)<<3)) 的方法將最高位右移至最低位，來判斷結(jié)果所有位是否為 0。

2.62

2.62.png

答案（兩種方法）：

int int_shifts_are_arithmetic_1(){
    return !(((0xFF<<((sizeof(int)-1)<<3))>>((sizeof(int)-1)<<3)) + 0x01 );
}

int int_shifts_are_arithmetic_2(){
    int x = -1;
    return (x>>1) == -1;
}

int main(void){ 
    int result_1 = int_shifts_are_arithmetic_1();
    printf("result_1 is: %d \n",result_1);
    int result_2 = int_shifts_are_arithmetic_2();
    printf("result_2 is: %d \n",result_2);
    return 1;
}

第一種方法，0xFF 先左移到最高字節(jié)，然后右移到最低字節(jié)，判斷其所有位是否為 1。
第二種方法，非常巧妙，通過 -1 既 0xFFFFFFFF 右移一位判斷其值是否改變。

2.63

2.63.png

答案：

unsigned srl(unsigned x, int k){
    unsigned xsra = (int) x >> k;
    int w = sizeof(int)*8;
    unsigned z = 2 << (w-k-1);
    return (z - 1) & xsra;
}

int sra(int x, int k){
    int xsrl = (unsigned) x >> k;
    int w = sizeof(int) << 3;
    unsigned z = 1 << (w-k-1);
    unsigned mask = z - 1;
    unsigned right = mask & xsrl;
    unsigned left = ~mask & (~(z&xsrl) + z);
    return left | right;
}

int main(void){ 
    unsigned result_srl = srl(-1,1);
    printf("result_srl is: %x \n",result_srl);
    int result_sra = sra(-1,1);
    printf("result_sra is: %x \n",result_sra);
    return 1;
}

運(yùn)行結(jié)果如下：

Result.png

對于 srl，目的就是將前面的高位清 0，即 xsra & (1<<(w-k) - 1)。額外注意 k==0 時，不能使用 1<<(w-k)，于是改用 2<<(w-k-1)。

注意，最大移位數(shù)不能夠 > w-1，因為移位數(shù)達(dá)到 w 之后的行為是未定義的，沒有標(biāo)準(zhǔn)。
對于形如 0x00001111 的情況，均可以使用 0x00010000 -1 的方式獲得。

對于 sra，目的是將 xrsl 的第 w-k-1 位擴(kuò)展到前面的高位。這個可以利用取反加 1 來實(shí)現(xiàn)，不過這里的加 1
是加 1<<(w-k-1)。如果 x 的第 w-k-1 位為 0，取反加 1 后，前面位全為 0，如果為 1，取反加 1 后就全是 1。最后再使用相應(yīng)的掩碼得到結(jié)果。

本題將第 w-k-1 位擴(kuò)展到前面高位的思想非常巧妙，需要根據(jù)代碼答案仔細(xì)體會。

2.64

2.64.png

答案：

int any_odd_one(unsigned x){
    return !!(x & 0x55555555);
}

int main(void){ 
    int result = any_odd_one(0xaaaaaaaa);
    printf("result is: %d \n", result);
    return 1;
}

此題思路是將偶數(shù)位全部取 0，奇數(shù)位不變。
需要注意的一點(diǎn)時，最后結(jié)果是 bool 類型，如果直接 x & 0x55555555 得出的不是 bool 類型，所以需要使用 ! 進(jìn)行轉(zhuǎn)換，既 !!(x & 0x55555555)。

2.65

2.65.png

答案：

int odd_ones(unsigned x){
    x = x ^ (x >> 1);  
    x = x ^ (x >> 2);  
    x = x ^ (x >> 4);  
    x = x ^ (x >> 8);  
    x = x ^ (x >> 16);  
    return x & 1;  
} 

int main(void){ 
    int result = odd_ones(9);
    printf("result is: %d \n", result);
    return 1;
}

由 1^1 = 0，1^0 = 1，0^0 = 0，可知，偶數(shù)個 1 異或的結(jié)果是 0，奇數(shù)個 1 異或的結(jié)果是 1。
比如，求 10101110 中的 1 的個數(shù)是奇數(shù)還是偶數(shù)，由 1^0^1^0^1^1^1^0 = 1 可知，個數(shù)為奇數(shù)。
所以我們得出結(jié)論，x 的每個位異或，最后的結(jié)果為 0，則有偶數(shù)個 1，為 1，則有奇數(shù)個 1。
回到本題，我們的目的是為了將 x 中的所有位的值進(jìn)行異或運(yùn)算，使用分治的思想：
x ^ (x >> 1) 表示 x 中的每一位和其后一位進(jìn)行異或，假設(shè)得到的結(jié)果為 x₁，則 x₁ 中的第 1 位的值表示 x 中第 1、2 位的異或結(jié)果，x₁ 中的第 3 位的值表示 x 中第 3、4 位的異或結(jié)果。
這個時候，x ^ (x >> 2) 既 x₁ ^ (x₁ >> 2)，表示 x₁ 中的每一位和其后第二位進(jìn)行異或，假設(shè)得到的結(jié)果為 x₂，則** x₂ 中的第 1 位的值表示 x₁ 中第 1、3 位的異或結(jié)果，既表示 x 中第 1、2、3、4 位的異或結(jié)果**，x₂ 中的第 5 位的值表示 x₁ 中第 5、7 位的異或結(jié)果，既表示 x 中第 5、6、7、8 位的異或結(jié)果。
根據(jù)以上可以推出，x ^ (x >> 4) 的結(jié)果 x₃ 的第一位表示 x₂ 的 1、5 位的異或結(jié)果，表示 x 的 1、2、3、4、5、6、7、8 位的異或結(jié)果。
同理，x ^ (x >> 8) 的結(jié)果 x₄ 的第一位表示 x 的 1 到 16 位的異或結(jié)果，x ^ (x >> 16) 的結(jié)果 x₅ 的第一位表示 x 的 1 到 32 位的異或結(jié)果。
所以，最后只有通過 x₅ & 1 來判斷 x₅ 的第一位是 0 還是 1 即可。

2.66

2.66.png

答案：

int leftmost_one(unsigned x){
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x^(x>>1);
}

int main(void){ 
    int result = leftmost_one(0x9f);
    printf("result is: %x \n", result);
    return 1;
}

根據(jù)提示，我們可以想到 00001111 ^ 00000111 = 00001000，所以接下來需要將 x 轉(zhuǎn)化為 [00…011…1] 的形式。
我們可以想到，用最高位的 1 分別與其他位進(jìn)行或運(yùn)算。
假設(shè) x 就是 10000000... 該如何讓每一位都為 1。方法如下：
- 先是 x 右移1位再和原 x 進(jìn)行或，變成 1100000...，再讓結(jié)果右移 2 位和原結(jié)果或，變成 11110000...，最后到 16 位，變成 11111111...。

2.67

2.67.png

答案：
A：1<<32 在 32 位機(jī)器上是未定義的。
B：將 1<<32 修改為 2<<31。
C：代碼如下：

int bad_int_size_is_32(){
    int a = 1<<15; 
    a<<=15; 
    int set_msb = a<<1; 
    int beyond_msb = a<<2;
    return set_msb && !beyond_msb;
}
int main(void){ 
    int result = bad_int_size_is_32();
    printf("result is: %d \n", result);
    return 1;
}

C 中需要將 31 拆分為 15+15+1。

2.68

2.68.png

答案：

int lower_one_mask(int n){
    return (2 << (n-1)) - 1;
}

int main(void){ 
    int result = lower_one_mask(32);
    printf("result is: %x \n", result);
    return 1;
}

2.69

2.69.png

答案：

unsigned rotate_left(unsigned x, int n){
    return (x << n)|(x >> 1 >> ((sizeof(int)*8)- n -1));
}

int main(void){ 
    unsigned result = rotate_left(0x12345678, 32);
    printf("result is: %x \n", result);
    return 1;
}

2.70

2.70.png

答案：

int fits_bits(int x, int n){
    x >>= (n-1);
    return !x || !(~x);
}

int main(void){ 
    int result = fits_bits(8, 4);
    printf("result is: %d \n", result);
    return 1;
}

這一題是看 x 的值是否在 - 2^(n-1) 到 2^(n-1) - 1 之間。
如果 x 滿足這個條件，則其第 n-1 位就是符號位。如果該位為 0，則前面的 w-n 位均為 0，如果該位為 1，則前面的 w-n 位均為1。所以本質(zhì)是判斷，x 的高 w-n+1 位是否為 0 或者為 -1。

2.71

2.71.png

答案：
A：得到的結(jié)果是 unsigned，而并非擴(kuò)展為 signed 的結(jié)果。
B：正確代碼如下：

int xbyte(packed_t word, int bytenum){
    int ret = word << ((3 - bytenum)<<3);
    return ret >> 24;
}

B 中使用 int，將待抽取字節(jié)左移到最高字節(jié)，再右移到最低字節(jié)即可。

2.72

2.72.png

答案
A：size_t 是無符號整數(shù)，因此左邊都會先轉(zhuǎn)換為無符號整數(shù)，它肯定是大于等于 0 的。
B：判斷條件改為 if(maxbytes > 0 && maxbytes >= sizeof(val))。

B 中為什么要先判斷 maxbytes > 0，是因為如果 maxbytes < 0，在執(zhí)行 maxbytes >= sizeof(val)) 時，會先將 maxbytes 轉(zhuǎn)化為無符號數(shù)，這樣就會導(dǎo)致結(jié)果與預(yù)期的不符合。

2.73

2.73.png

答案

#include <limits.h>

int saturating_add(int x, int y){
    int w = sizeof(int)<<3;
    int t = x + y;
    int ans = x + y;
    x>>=(w-1);
    y>>=(w-1);
    t>>=(w-1);
    int pos_ovf = ~x&~y&t;
    int neg_ovf = x&y&~t;
    int novf = ~(pos_ovf|neg_ovf);
    return (pos_ovf & INT_MAX) | (novf & ans) | (neg_ovf & INT_MIN);
} 

int main(void){ 
    int result = saturating_add(INT_MIN, -1);
    printf("result is: %x \n", result);
    return 1;
}

解析

對于有符號整數(shù)相加，溢出的規(guī)則可以總結(jié)為：
- t = a+b。
- 如果 a，b 異號，則肯定不會溢出。
- 如果 a，b 中有一個為 0，則肯定不會溢出。
- 如果 a>0 && b>0，則只有當(dāng) t<0 時才算正溢出。
- 如果 a<0 && b<0，則只有當(dāng) t>0 時才算負(fù)溢出。
- 所以：
  - a > 0，b > 0，t < 0，正溢出。
  - a < 0，b < 0，t > 0，負(fù)溢出。

思路

碰到一個復(fù)雜問題時，如果一下子無法看出規(guī)律，應(yīng)該要善于總結(jié)條件和推理結(jié)果，從這個過程中尋找規(guī)律。

2.74

2.74.png

答案

#include <stdint.h>

int tsub_ok(int x, int y){
    int w = sizeof(int)<<3;
    int t = x - y;
    x>>=(w-1);
    y>>=(w-1);
    t>>=(w-1);
    return !((x != y) && (y == t));
}

int main(void){ 
    int result = tsub_ok(INT32_MIN, 1);
    printf("result is: %d \n", result);
    return 1;
}

對于有符號整數(shù)相減，溢出的規(guī)則可以總結(jié)為：
- t = a-b。
- 如果 a，b 同號，則肯定不會溢出。
- 如果 a，b 中有一個為 0，則肯定不會溢出。
- 如果 a>0 && b<0，則只有當(dāng) t<0 時才算溢出。
- 如果 a<0 && b>0，則只有當(dāng) t>0 時才算溢出。
- 所以，a，b 異號，t，b 同號即可判定為溢出。

2.75

2.75.png

答案

unsigned unsigned_high_prod(unsigned x, unsigned y){
    int w = sizeof(int)<<3;
    return signed_high_prod(x, y) + ((int)x>>(w-1)) & y + ((int)y>>(w-1)) & x;
}

假如 x'、y' 分別表示 2 的補(bǔ)碼表示的有符號數(shù) x、y 對應(yīng)的無符號數(shù)，x_w-1、y_w-1 分別表示有符號數(shù) x、y 的最高位符號位，則在數(shù)據(jù)類型 unsigned 是 w 位的機(jī)器上，有如下結(jié)論：
- x' = x + x_w-1 * 2^w
- y' = y + y_w-1 * 2^w
- x'y' = xy + x * y_w-1 * 2^w + y * x_w-1 * 2^w + x_w-1 * y_w-1 * 2^2w
我們知道，在 w 位機(jī)器上，無論是有符號數(shù)，還是無符號數(shù)，乘法的本質(zhì)是將結(jié)果 2w 位截斷為低 w 位，然后再用相應(yīng)的有符號數(shù)或無符號數(shù)表示。所以，乘法結(jié)果的高 w 位表示需要在乘法結(jié)果的基礎(chǔ)上右移 w 位，即除以 2^w，假設(shè) x'y'_h、xy_h 分別為其乘積的高位表示，則有如下結(jié)論：
- x'y'_h = xy_h + x * y_w-1 + y * x_w-1 + x_w-1 * y_w-1 * 2^w
- 由于 x'y'_h 只有 w 位，所以 x_w-1 * y_w-1 * 2^w 最后會被截斷掉，對結(jié)果沒有影響，則有如下結(jié)論：
  - x'y'_h = xy_h + x * y_w-1 + y * x_w-1
由于本題要求遵循位級編碼規(guī)則，即不能使用乘號，所以可以進(jìn)行如下變換，巧妙的使用 int 進(jìn)行移位，并進(jìn)行與運(yùn)算：
- x * y_w-1 = x * (y>>(w-1)) = ((int)y >> (w-1)) & x
- y * x_w-1 = y * (x>>(w-1)) = ((int)x >> (w-1)) & y
所以最后結(jié)果為：
- x'y'_h = xy_h + ((int)y >> (w-1)) & x + ((int)x >> (w-1)) & y

2.76

2.76.png

答案
//TODO

2.77

2.77.png

答案
A. (x << 4) + x
B. x - (x << 3)
C. (x << 6) - (x << 2)
D. (x << 4) - (x << 7)

2.78

2.78.png

答案

int divide_power2(int x, int k){
    int ans = x>>k;
    int w = sizeof(int)<<3;
    ans += (x>>(w-1)) && (x&((1<<k)-1));
    return ans;
}

首先計算 x>>k。
然后考慮除法的向零舍入，即 x<0 且 x 的最后 k 位不為零時要加一。
- 必須保證除法是向零舍入的。
- 當(dāng) x>0 時，x>>k 的結(jié)果是向下舍入的，由于 x 是正數(shù)，所以是向零舍入，符合要求。
- 當(dāng) x<0 且 x 的最后 k 位不為零時，x>>k 的結(jié)果是向下舍入的，由于 x 是負(fù)數(shù)，此時向下舍入后的值不符合向零舍入的目的，需要將結(jié)果加一才符合向零舍入。

2.79

2.79.png

答案

// TODO

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【CS:APP】第二章家庭作業(yè)

【CS:APP】第二章家庭作業(yè)

2.55 - 2.57

2.58

2.59

2.60

位級整數(shù)編碼規(guī)則

2.61

2.62

2.63

2.64

2.65

2.66

2.67

2.68

2.69

2.70

2.71

2.72

2.73

2.74

2.75

2.76

2.77

2.78

2.79

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【CS:APP】第二章 家庭作業(yè)

2.55 - 2.57

2.58

2.59

2.60

位級整數(shù)編碼規(guī)則

2.61

2.62

2.63

2.64

2.65

2.66

2.67

2.68

2.69

2.70

2.71

2.72

2.73

2.74

2.75

2.76

2.77

2.78

2.79

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【CS:APP】第二章家庭作業(yè)