CSAPP_CHAPTER_2_HOMEWORK

2.55

见2.56

2.56

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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_int(int x){
   show_bytes((byte_pointer) &x, sizeof(int));
}

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


void show_pointer(void *x){
   show_bytes((byte_pointer) &x, sizeof(void *));
}

void test_show_bytes(int val){
   int ival = val;
   float fval = (float)ival;
   int *pval = &ival;
   show_int(ival);
   show_float(fval);
   show_pointer(pval);


   // 2.57
   //---
   puts("2.57");

   short sval = (short)ival;
   long lval = (long)ival;
   double dval = (double)ival;

   show_short(sval);
   show_long(lval);
   show_double(dval);
   //---
   
}

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

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

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

//---
int main(void){

   int x;
   scanf("%d", &x);
   test_show_bytes(x);

   puts("");
   return 0;
}

结果

Linux 上的结果

Linux中运行结果，可以发现是小端法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root@DAT:/mnt/d/desktop/documents/code/csapplab/2_homework# ./2.55
114514
 52 bf 01 00
 00 a9 df 47
 78 72 e5 d3 ff 7f 00 00
root@DAT:/mnt/d/desktop/documents/code/csapplab/2_homework# ./2.55
0
 00 00 00 00
 00 00 00 00
 b8 73 fd dc ff 7f 00 00
root@DAT:/mnt/d/desktop/documents/code/csapplab/2_homework# ./2.55
16
 10 00 00 00
 00 00 80 41
 b8 69 30 db ff 7f 00 00

Windows 上的结果

Windows中运行结果，可以发现也是小端法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
114514
 52 bf 01 00
 00 a9 df 47
 cc fd 61 00 00 00 00 00
PS D:\desktop\documents\code\csapplab>  & 'c:\Users\zheng\.vscode\extensions\ms-vscode.cpptools-1.17.5-win32-x64\debugAdapters\bin\WindowsDebugLauncher.exe' '--stdin=Microsoft-MIEngine-In-x3kk2v00.wpa' '--stdout=Microsoft-MIEngine-Out-vce5bszq.mhh' '--stderr=Microsoft-MIEngine-Error-p2lagywq.jry' '--pid=Microsoft-MIEngine-Pid-b1hpb53h.4bh' '--dbgExe=C:\mingw64\bin\gdb.exe' '--interpreter=mi' 
0
 00 00 00 00
 00 00 00 00
 cc fd 61 00 00 00 00 00
PS D:\desktop\documents\code\csapplab>  & 'c:\Users\zheng\.vscode\extensions\ms-vscode.cpptools-1.17.5-win32-x64\debugAdapters\bin\WindowsDebugLauncher.exe' '--stdin=Microsoft-MIEngine-In-mmc2dxkn.amd' '--stdout=Microsoft-MIEngine-Out-m4qg0ap5.kgr' '--stderr=Microsoft-MIEngine-Error-vzt24roe.yow' '--pid=Microsoft-MIEngine-Pid-amzgwdkd.ibt' '--dbgExe=C:\mingw64\bin\gdb.exe' '--interpreter=mi' 
16
 10 00 00 00
 00 00 80 41
 cc fd 61 00 00 00 00 00
PS D:\desktop\documents\code\csapplab>

总结

可以发现，对于相同的数字，他们在都是小端法的不同机器上有着相同的位表示，但是对于指针的位表示有着很大的差别。

2.57

code

1
//2.55~2.56中有

结果

Linux 上的运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
root@DAT:/mnt/d/desktop/documents/code/csapplab# ./2_homework/2_55
114514
 52 bf 01 00
 00 a9 df 47
 58 6d 8a f2 ff 7f 00 00
2.57
 52 bf
 52 bf 01 00 00 00 00 00
 00 00 00 00 20 f5 fb 40

root@DAT:/mnt/d/desktop/documents/code/csapplab# ./2_homework/2_55
0
 00 00 00 00
 00 00 00 00
 58 e3 56 e4 ff 7f 00 00
2.57
 00 00
 00 00 00 00 00 00 00 00
 00 00 00 00 00 00 00 00

root@DAT:/mnt/d/desktop/documents/code/csapplab# ./2_homework/2_55
16
 10 00 00 00
 00 00 80 41
 78 f1 5b df ff 7f 00 00
2.57
 10 00
 10 00 00 00 00 00 00 00
 00 00 00 00 00 00 30 40

Windows 上的运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
PS D:\desktop\documents\code\csapplab>  & 'c:\Users\zheng\.vscode\extensions\ms-vscode.cpptools-1.17.5-win32-x64\debugAdapters\bin\WindowsDebugLauncher.exe' '--stdin=Microsoft-MIEngine-In-h542cx5h.1vh' '--stdout=Microsoft-MIEngine-Out-dr1m4jov.55a' '--stderr=Microsoft-MIEngine-Error-2kfssydw.n4g' '--pid=Microsoft-MIEngine-Pid-qqnvig5v.3ps' '--dbgExe=C:\mingw64\bin\gdb.exe' '--interpreter=mi mingw64/bin/gdb.exe' 
114514
 52 bf 01 00
 00 a9 df 47
 bc fd 61 00 00 00 00 00
2.57
 52 bf
 52 bf 01 00
 00 00 00 00 20 f5 fb 40

PS D:\desktop\documents\code\csapplab>  & 'c:\Users\zheng\.vscode\extensions\ms-vscode.cpptools-1.17.5-win32-x64\debugAdapters\bin\WindowsDebugLauncher.exe' '--stdin=Microsoft-MIEngine-In-ayggdlku.2vt' '--stdout=Microsoft-MIEngine-Out-k1nqv0f3.t41' '--stderr=Microsoft-MIEngine-Error-o5hsig5b.hoy' '--pid=Microsoft-MIEngine-Pid-wz1dvk4t.4kt' '--dbgExe=C:\mingw64\bin\gdb.exe' '--interpreter=mi mingw64/bin/gdb.exe' 
0
 00 00 00 00
 00 00 00 00
 bc fd 61 00 00 00 00 00
2.57
 00 00
 00 00 00 00
 00 00 00 00 00 00 00 00

PS D:\desktop\documents\code\csapplab>  & 'c:\Users\zheng\.vscode\extensions\ms-vscode.cpptools-1.17.5-win32-x64\debugAdapters\bin\WindowsDebugLauncher.exe' '--stdin=Microsoft-MIEngine-In-lrmm2cxo.gyo' '--stdout=Microsoft-MIEngine-Out-lzge0kqy.g0f' '--stderr=Microsoft-MIEngine-Error-5obra5ki.dwg' '--pid=Microsoft-MIEngine-Pid-1ndcgvzc.z3g' '--dbgExe=C:\mingw64\bin\gdb.exe' '--interpreter=mi mingw64/bin/gdb.exe' 
16
 10 00 00 00
 00 00 80 41
 bc fd 61 00 00 00 00 00
2.57
 10 00
 10 00 00 00
 00 00 00 00 00 00 30 40

总结

可以发现对于同一个数字，short、long、double这几类他们在这两个不同机器上的位表示依然一致。目前发现只有指针的位表示在不同机器上有着很大的差别。

2.58

因为我只能在Linux和Windows这两种小端法机器运行，所以没办法校验这个程序的正确性了。反正用的方法特别蠢，就是看对于0x1他是正序还是逆序输出。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>

typedef unsigned char *byte_pointer;

int is_little_endian(){
    const int x = 0x1;
    return show_bytes((byte_pointer) &x, sizeof(x));
}

int show_bytes(byte_pointer start, size_t len){
    size_t i;
    return (int)start[0] == 1;
}

int main(void){
    printf("%d\n", is_little_endian());
    return 0;  
}

结果

1
2
3
1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-bm35uzzy.zuk" 1>"/tmp/Microsoft-MIEngine-Out-bkoz1q1g.3bj"
root@DAT:/mnt/d/desktop/documents/code/csapplab#

2.59

利用掩码和位运算获取对应位置的字符

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>

typedef unsigned char *byte_pointer;

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

int main(void){
  
    int x, y;
    x = 0x89ABCDEF; // 最低有效字节，也就是最低的8位，在这里就是EF。
    y = 0x76543210;

    // 设置掩码
    int mask1 = 0xFF;
    int mask2 = ~mask1;

    //利用设置的掩码获取x的最低有效字节和y的其余字节
    int a = x & mask1;
    int b = y & mask2;

    //合并
    int res = a | b;

    //debug
    puts("---debug---");
    show_bytes((byte_pointer) &x, sizeof(x));
    show_bytes((byte_pointer) &y, sizeof(y));

    show_bytes((byte_pointer) &mask1, sizeof(mask1));
    show_bytes((byte_pointer) &mask2, sizeof(mask2));

    show_bytes((byte_pointer) &a, sizeof(a));
    show_bytes((byte_pointer) &b, sizeof(b));

    show_bytes((byte_pointer) &res, sizeof(res));
  
    puts("");
    puts("");
    puts("");

  
    puts("---Result---");
    printf("%x\n", res);




    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---debug---
efcdab89
10325476
ff000000
00ffffff
ef000000
00325476
ef325476



---Result---
765432ef
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-vd15og4p.eon" 1>"/tmp/Microsoft-MIEngine-Out-poicrtxv.cbl"

2.60

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>

// 2.60
unsigned replace_byte(unsigned x, int i, unsigned char b);

unsigned replace_byte(unsigned x, int i, unsigned char b){
    //将b移到正确位置
    unsigned op1 = b << (i * 8);
    //设置掩码
    unsigned mask1 = (0xFF << (i * 8));

    unsigned temp1 = mask1 & op1;
    unsigned temp2 = ~mask1 & x;
    unsigned res = temp1 | temp2;

    return res;
}


int main(void){

    printf("%.2X\n", replace_byte(0x12345678, 2, 0xAB));
    printf("%.2X\n", replace_byte(0x12345678, 0, 0xAB));
  
    return 0;
}

结果

1
2
3
12AB5678
123456AB
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-jcvdupw1.gby" 1>"/tmp/Microsoft-MIEngine-Out-tryz424p.yil"

总结

和书上一模一样

2.61

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int main(void) {
    int x;

    // 测试：
    // x全0
    // x = 0x0;
    // //x全1
    // x = ~(0x0);
    // //x最低有效字节为1
    // x = 0x114514FF;
    // //x最高有效字节为0
    x = 0x00114514;
    // // 其他情况
    // x = 0x11451419;

    //全0
    int m1 = 0x0;
    //全1
    int m2 = ~m1;

    //最低位单字节掩码
    int m3 = 0xFF;
    //最高位单字节掩码
    int m4 = m3 << (sizeof(x) - 1 << 3);
    //如果x是全0。
    int res1 = x;

    //如果x是全1。-1 + 1 == 0。
    int res2 = x + 0x1;

    //如果x最低有效位字节全1
    //先提取最低有效位字节
    int t1 = x & m3;
    int res3 = t1;

    //如果x最高有效位字节全0
    //先提取最高有效位字节
    int t2 = x & m4;
    int res4 = t2;

    //如果上述四种情况res有一个为0，则产生1。

    int res = !res1 || !res2 || !res3 || !res4;


    printf("x为:%.8X, res:%d\n",x, res);

    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

x为:00000000, res:1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-5k4l4vyj.1pz" 1>"/tmp/Microsoft-MIEngine-Out-oei23k3f.adw"
root@DAT:/mnt/d/desktop/documents/code/labs# 

x为:FFFFFFFF, res:1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-tvcbzgms.sca" 1>"/tmp/Microsoft-MIEngine-Out-dry20vkj.rji"
root@DAT:/mnt/d/desktop/documents/code/labs# 

x为:114514FF, res:0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-qqvc5ywk.krd" 1>"/tmp/Microsoft-MIEngine-Out-law5jpe3.nsa"
root@DAT:/mnt/d/desktop/documents/code/labs# 

x为:00114514, res:1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-plck3i4f.f1y" 1>"/tmp/Microsoft-MIEngine-Out-oqwl5e5w.so0"
root@DAT:/mnt/d/desktop/documents/code/labs# 

x为:11451419, res:0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-0botd1ci.nbv" 1>"/tmp/Microsoft-MIEngine-Out-y4hyrjgv.te1"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

输出符合预期，不过其实全1和全0的情况其实是后两种情况的子集，没必要单独写的。

2.62 *

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int int_shifts_are_arithmetc(){
    //先让x最高位 置1
    int x = (0x1) << (sizeof(x) << 3) - 1;

    //如果是算数右移，x应该是0x0。
    x = (x >> (sizeof(x) << 3) - 1) + 1; 

    //如果是逻辑右移，x应该是0x2
    x = ((unsigned)x >>  (sizeof(x) << 3 ) - 1) + 1;

    return  !x;
}

int main(void) {
    printf("%d\n", int_shifts_are_arithmetc());
    return 0;
}

结果

算数右移

1
2
3
1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-sz2f0153.k1u" 1>"/tmp/Microsoft-MIEngine-Out-pzwl3qdm.euj"
root@DAT:/mnt/d/desktop/documents/code/labs#

逻辑右移

1
2
3
0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-tzysjmho.m4e" 1>"/tmp/Microsoft-MIEngine-Out-nghzhqry.5wk"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

哎，机器太少了，想多测试都没法。只能用 (unsigned)x
来凑合凑合了。

2.63 *

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

// 哇，这题有点东西的。

//利用算数右移完成逻辑右移
unsigned srl(unsigned x, int k){
    /* Perform shift arithmetically*/
    unsigned xsra = (int) x >> k;


    int w = sizeof(x) * 8;   // 题目允许哈
    //从(w-2)-(k-1) ~ (w-2)的(k-1)位从1变成0
    //因为不能右移，所以要麻烦一点。因为最后是与运算，而且是“消除1”的操作，所以直接干就完事，
    //不需要判断最高位是不是1。

    /*
    思路：
    逻辑右移：
    对于有符号数：  （x代表不关心具体是什么)
    1xxx xxxx xxxx .... xxxx
    右移k位
    想让他从
    1111 .... 1xxx .... xxxx
    变成
    0000 .... 1xxx .... xxxx
    就是需要把高位被置1的数变成0，
    而右移k位的过程中，有k-1个数被置1了(不包括右移操作后的1当前的位置)。
    然后我们把这k-1个数变回0，只要用高k-1个位为0，其余都是1的掩码和xsra相与即可。
    掩码应该类似：0000 .... 1111 .... 1111
    首先，先获取k-1个1。由于不能用算数右移的置1特性，这里就用1000 - 1 == 0111的特性。
    让0x1左移k位，然后减一，就可以得到k-1个1了。
    接下来就是将这k-1个1移到最高位，让高位k-1个位变成全1，也就是左移w-(k-1)-1位。
    然后对其取反就可以得到想要的掩码了。
    */

    //获取k-1个1。
    int mask = (0x1 << ((k - 1) + 1)) - 1;
    //然后左移w-(k-1)-1位
    mask = mask << (w-(k-1)-1);
    //把想要操作的对应位变成0
    mask = ~mask;

    xsra = mask & xsra;

    return xsra; 
}


//利用逻辑右移完成算数右移
int sra(int x, int k){
    /* Perform shift logically*/
    int xsrl = (unsigned) x >> k;

    int w = sizeof(x) * 8;   // 题目允许哈
  
    //大体同上，不过因为最后是或运算，而且是“添加1”的操作，所以还需要判断最高位是不是1，
    //只对最高位位1的数进行算数右移。

    //获取最高位。同样的，因为不能使用右移，所以要麻烦一丢丢。
    //首先获取最高位的掩码1000 .... 0000
    int top = 0x1 << (w - 1);
    //对于最高位为1，s为全1，否则为全0
    int s = top & xsrl;
    s = top - s; //如果最高位是1，s = 0，最高位是0，s = 1000 .... 0000。
    s = !!s; //如果最高位是1，s = 0，最高位是0，s = 1
    s = ~(~s + 0x1); //利用~x + 1 == -x 和 -0 == 0, -1 == 0XFFF...F，获取全1/0掩码。

    //获取k-1个1。
    int mask = (0x1 << ((k - 1) + 1)) - 1;
    //然后左移w-(k-1)-1位
    mask = mask << (w-(k-1)-1);
  
    //把想要操作的对应位变成1,所以不用取反。不过这里就用或了。
    //如果最高位是1就操作，否则不变
    xsrl = s & (mask | xsrl) | ~s & xsrl;

    return xsrl;
}


int main(void) {
  
    int x = 0x01234567;
    int k = sizeof(x) * 5;
  
    puts("srl:");
    printf("%.8X\n%.8X\n", srl(x, k), (unsigned)x >> k);

    puts("sra:");
    printf("%.8X\n%.8X\n", sra(x, k), x >> k);

    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
srl:
00080123
00080123
sra:
FFF80123
FFF80123
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-4ihywx3n.0jn" 1>"/tmp/Microsoft-MIEngine-Out-tnmba0ls.ez5"
root@DAT:/mnt/d/desktop/documents/code/labs# 


srl:
000F0123
000F0123
sra:
FFFF0123
FFFF0123
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-omnlf5ds.duu" 1>"/tmp/Microsoft-MIEngine-Out-vhqrrczp.vue"
root@DAT:/mnt/d/desktop/documents/code/labs# 


srl:
00000012
00000012
sra:
00000012
00000012
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-zrig3030.ubw" 1>"/tmp/Microsoft-MIEngine-Out-sadgltcj.3c4"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

难点：

    1. 不能用右移来获得掩码，很难受。
    1. 对于逻辑右移完成算数右移还需要多一步判断。
    1. 写题的时候肚子饿了。

2.64

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/* Return 1 when any odd bit of x equals 1; 0 otherwise, 
   Assume w=32 */
int any_odd_one(unsigned x);

int any_odd_one(unsigned x){
    //所有奇数位中只要有1就返回1，所以如返回一个奇数位全为1的掩码和x的相与就行。
    return !!(0xAAAAAAAA & x);
}

int main(void) {
    //0x55555555  偶数位全0
    //0xAAAAAAAA  奇数位全1
    int x = 0x55555555;
    printf("%d\n", any_odd_one(x));
    return 0;
}

结果

1
2
3
4
5
6
7
0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-jza3abtb.tun" 1>"/tmp/Microsoft-MIEngine-Out-m223vapc.lgg"
root@DAT:/mnt/d/desktop/documents/code/labs# 

1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-a5d2rqvu.hha" 1>"/tmp/Microsoft-MIEngine-Out-v51cyks4.1rf"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.65 **

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。 
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/* Return 1 when x contains an odd number of 1s; 0 otherwise
   Assume w=32 */
int odd_ones(unsigned x);

// 四星题，别急慢慢想，已经没有比这更难的了，别急别慌。
// 鉴于这题的难度和限制运算符数量，所以肯定不可能逐位取出，而是用其他方法。
int odd_ones(unsigned x){
    // 最后只能想到异或了，因为异或是不同取1，相同取0。可以把两个相邻的数看成一个基本单元，一个单元的两个数异或，
    // 取1必定是有奇数个1，但是对于两个相邻的单元，如果都是奇数，也就是都是1，对这两个单元异或最后取0，,也符合奇数+奇数等于偶数，
    // 所以最后两个包含16个数的单元异或可以获得整个x的奇偶数信息。妈的，太绝了。
    // 当然上面只是为了方便理解说的，实际操作直接把两个16位的大单元异或，最后得到的就是包含8个两两数字之间的奇偶信息。然后以此类推
    // 最后就可以获得整个x的奇偶数信息。
    unsigned x_16 = (x >> 16) ^ x; //高16位和低16位相与，最后低16位是奇偶信息
    unsigned x_8 = (x_16 >> 8) ^ x_16;
    unsigned x_4 = (x_8 >> 4) ^ x_8;
    unsigned x_2 = (x_4 >> 2) ^ x_4;
    unsigned x_1 = (x_2 >> 1) ^ x_2;
    return !!(x_1 << 31);
}

int main(void) {
    //unsigned x = 0xFFFFFFFF;
    //unsigned x = 0xFFF1FFFF;
    unsigned x = 0x11451411;
    printf("%d\n", odd_ones(x));
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-21tjg1z2.213" 1>"/tmp/Microsoft-MIEngine-Out-i1nuiihw.rd5"
root@DAT:/mnt/d/desktop/documents/code/labs# 


1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-jqatywc5.5ds" 1>"/tmp/Microsoft-MIEngine-Out-iwgjhdtd.1yj"
root@DAT:/mnt/d/desktop/documents/code/labs# 


1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-celqnh4f.zaf" 1>"/tmp/Microsoft-MIEngine-Out-vjdk2bga.5ix"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

这道题太特么有意思了，利用异或的和奇偶数的特性巧妙的将原本需要按位遍历$w$次，转变成只需要$ \log_{2}w $次。

2.66 *

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/*
 * Generate mask indicating leftmost 1 in x.    Assume w=32.
 * For example, 0xFF00 -> 0x8000, and 0x6600 --> 0x4000.
 * If x = 0, then return 0.
 */
int leftmost_one(unsigned x);

//应该是二分找到最左边的1，如果没找到1就舍弃对应区间。
int leftmost_one(unsigned x){

    unsigned isZero = !!x;
    int sum = 0;
  
    //先看高位16，看他有没有1，如果有就从高位16开始划分，如果没有就舍弃。
    //如果高16位有1，那就从+16，同时x右移16位，只看保留位。
    int b16 = !!(x >> 16) << 4;
    x >>= b16;

    //然后继续判断保留的16位中的高8位。
    int b8 = !!(x >> 8) << 3;
    x >>= b8;

    int b4 = !!(x >> 4) << 2;
    x >>= b4;

    int b2 = !!(x >> 2) << 1;
    x >>= b2;

    int b1 = !!(x >> 1);
    x >>= b1;
  
    //然后累加
    sum = b16 + b8 + b4 + b2 + b1;
  
    return (isZero << sum);
}
int main(void) {
    int x = 0x6600;
    printf("%.8X\n", leftmost_one(x));
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
00008000
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-hixnj1og.sqv" 1>"/tmp/Microsoft-MIEngine-Out-bmkiksag.vsj"
root@DAT:/mnt/d/desktop/documents/code/labs# 

00004000
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-yzin1hjv.io2" 1>"/tmp/Microsoft-MIEngine-Out-vt0dtm2w.mhs"
root@DAT:/mnt/d/desktop/documents/code/labs# 

10000000
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-izakqp5x.ftg" 1>"/tmp/Microsoft-MIEngine-Out-au1ywcrk.zq4"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

这题利用了二分的思想和高低位的关系来求解，和上题一样，只需要$ \log_{2}w $次就能得到结果。

2.67

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/


// /* The following code does not run properly on some machines */
// int bad_int_size_is_32(){
//     /* Set most significant bit (msb) of 32-bit machine */
//     int set_msb = 1 << 31;
//     /* Shift pase msb of 32-bit word */
//     int beyond_msb = 1 << 32;

//     /* set_msb is nonzero when word size >= 32
//        beyond_msb is zero when word size <= 32  */
//     return set_msb && !beyond_msb;
// }
//不让用sizeof()

// A.
/* 不应该显式的越界 */
// B.
int int_size_is_32(){
    /* Set most significant bit (msb) of 32-bit machine */
    int set_msb = 1 << 31;
    /* 利用加法进位溢出而不是直接移位溢出 */
    int beyond_msb = set_msb + set_msb;

    /* set_msb is nonzero when word size >= 32
       beyond_msb is zero when word size <= 32  */
    return set_msb && !beyond_msb;
}


// C.
int int_size_is_16(){
    /* Set most significant bit (msb) of 16-bit machine */
    int set_msb = 1 << 16;
    /* 利用加法进位溢出而不是直接移位溢出 */
    int beyond_msb = set_msb + set_msb;

    /* set_msb is nonzero when word size >= 16
       beyond_msb is zero when word size <= 16  */
    return set_msb && !beyond_msb;
}

int main(void) {
    printf("%d\n", int_size_is_32());
    printf("%d\n", int_size_is_16());
    return 0;
}

结果

1
2
3
4
1
0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-spybbu4f.tih" 1>"/tmp/Microsoft-MIEngine-Out-4xiozkhn.wml"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.68

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/*
 * Mask with least signficant n bits set to 1 
 * Examples: n = 6 --> 0x3F, n = 17 -->0x1FFFF
 * Assume 1 <= n <=w
 */
int lower_one_mask(int n);

int lower_one_mask(int n){
    int w = sizeof(n) << 3;
    //当w=n时，设置掩码。
    int mask = ((!!(w - n)) << (w - 1)) >> (w - 1);
    //当w=n时 res恰好也是~mask
    int res = ~(((0x1 << (w - 1))) >> (w - 1 - n)) & mask | ~mask;
    return res;
}
int main(void) {
    int n = 6;
    printf("%.8X\n", lower_one_mask(n));
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

0000003F
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-pf0aul3d.xrt" 1>"/tmp/Microsoft-MIEngine-Out-zibkafs5.l20"
root@DAT:/mnt/d/desktop/documents/code/labs# 

0001FFFF
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-t0tcakqx.m5z" 1>"/tmp/Microsoft-MIEngine-Out-supk3mwg.uni"
root@DAT:/mnt/d/desktop/documents/code/labs# 

00000001
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-al4vs5l0.m2f" 1>"/tmp/Microsoft-MIEngine-Out-p4yyq1ia.ct4"
root@DAT:/mnt/d/desktop/documents/code/labs# 

FFFFFFFF
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-33dzhesj.lpb" 1>"/tmp/Microsoft-MIEngine-Out-gdxxwx21.tyx"
root@DAT:/mnt/d/desktop/documents/code/labs#


2.69

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/*
 * Do rotating left shift.  Assume 0 <= n <= w
 * Examples when x = 0x12345678 and w = 32:
 *     n=4 -> 0x23456781, n=20 -> 0x67812345
 */
unsigned rotate_left(unsigned x, int n);

unsigned rotate_left(unsigned x, int n){
    int w = sizeof(n) << 3;

    //首先提取高n位的数据制成掩码，然后提取将提取数据的补集制成掩码，
    //最后将补集数据左移n位，然后将高n位数据右移到最低位，然后合并两条数据

    unsigned x_high = (x >> (w - n)); 
    printf("%.8X\n", x_high);
    unsigned x_low =  (x << n);
    printf("%.8X\n", x_low);

    return x_low | x_high;
}
int main(void) {
    int x = 0x12345678;
    int n = 4;

    printf("%.8X\n", rotate_left(x, n));
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
23456781
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-2kcesupy.go2" 1>"/tmp/Microsoft-MIEngine-Out-5tkfyr1i.wm4"
root@DAT:/mnt/d/desktop/documents/code/labs# 

67812345
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-4tctt5ta.r4f" 1>"/tmp/Microsoft-MIEngine-Out-slvpdar4.tvk"
root@DAT:/mnt/d/desktop/documents/code/labs# 

12345678
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-uakzwkzd.42h" 1>"/tmp/Microsoft-MIEngine-Out-b02oi4a5.kyz"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.70

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/


/* 
 * Return 1 when x can be represented as an n-bit, 2's-complement
 * number; 0 otherwise
 * Assume 1 <= n <= w
 */
int fits_bits(int x, int n);

// 当x可以被n位的二进制表达的时候返回1
int fits_bits(int x, int n){

    int w = sizeof(x) << 3;
    //将x和n位二进制的最大值比较即可，当x小于等于它时就返回1
    //也就是低n位全1
    int n_1 = ~((0x1 << (w - 1)) >> (w - n - 1));
    // 也就是n_1 - x >= 0。只要判断符号位是不是1就行了
    int res = !!((~x + n_1 + 1) >> (w - 1));
  
    return !res;
}
int main(void) {
    int x = 0xFFFF;
    int n = 8;
    printf("%d\n", fits_bits(x, n));
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13

0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-g3t5qfh4.5bs" 1>"/tmp/Microsoft-MIEngine-Out-cda1gsjz.sre"
root@DAT:/mnt/d/desktop/documents/code/labs# 


0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-yakvbt41.ivo" 1>"/tmp/Microsoft-MIEngine-Out-lsuy4bk0.wog"
root@DAT:/mnt/d/desktop/documents/code/labs# 

1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-upxiuguf.vsr" 1>"/tmp/Microsoft-MIEngine-Out-i3jldpzr.qdp"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.71

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/* Declaration of data type where 4 bytes are packed
   into an unsigned */
typedef unsigned packed_t;

/* Extract byte from word. Return as signed integer */
int xbyte(packed_t word, int bytenum);

int xbyte(packed_t word, int bytenum){
    int w = sizeof(word) << 3;
    unsigned origin = word >> (bytenum << 3) & 0xFF;
    int sign = (int)(origin << (w - 8)) >> (w - 8);

    return sign;
}


int main(void) {
    packed_t word = 0x88BBCCDD;
    int bytenum = 3;
    printf("%.8X\n", xbyte(word, bytenum));
    return 0;
}

结果

1
2
3
4

FFFFFF88
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-txs4w3kh.ccw" 1>"/tmp/Microsoft-MIEngine-Out-4byd23rl.dwl"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.72

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <string.h>


/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/
/* Copy integer into buffer if space is available */
void copy_int(int val, void *buf, int maxbytes);

void copy_int(int val, void *buf, int maxbytes){
    //A. 因为sizeof返回类型是long unsigned，而参与运算的另一个变量是int类型，
    //   最后运算的结果会被隐式的转换成long unsigned，而无符号数总是>=0。

    //B. 将sizeof强制转换成int即可。所以判断最高符号位就行。
    if(!((maxbytes - (int)sizeof(val)) >> 31))
        puts("TEST");
        memcpy(buf, (void *) &val, sizeof(val));
}


int main(void) {
    int val = 1;
    void *buf;
    int maxbytes = 1;
    copy_int(val, buf, maxbytes);

    return 0;
}

结果

1
2
3
4
5
6
7
TEST
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-40osa1p4.zui" 1>"/tmp/Microsoft-MIEngine-Out-vhn5v3ga.tap"
root@DAT:/mnt/d/desktop/documents/code/labs# 

[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-m42u5let.po0" 1>"/tmp/Microsoft-MIEngine-Out-5y3yvhsy.mka"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.73

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/


/* Addition that saturates to TMin or TMax */
int saturating_add(int x, int y);

// 加法，正溢出返回TMax，负溢出返回TMin。
int saturating_add(int x, int y){
    int w = sizeof(x) << 3;
    // 如果相加正溢出，则x < 0, y < 0，但是x + y > 0
    // 如果相加负溢出，则x > 0, y > 0，但是x + y < 0
    int isneg_x = !!(x >> (w - 1));
    int isneg_y = !!(y >> (w - 1));
  

    // 制成他们对应的全1掩码
    int isneg_both = (isneg_x && isneg_y);
    int ispos_both = (!isneg_x && !isneg_y);
    int pos_sat = ~(isneg_both && !((x + y) >> (w - 1))) + 1; 
    int neg_sat = ~(ispos_both && ((x + y) >> (w - 1))) + 1;
    int TMin = 0x1 << (w - 1);
    int TMax = ~TMin;
    return (~neg_sat & ~neg_sat & (x + y)) | (neg_sat & TMin) | (pos_sat & TMax);
}
int main(void) {
    int w = sizeof(int) << 3;
    int TMin = 0x1 << (w - 1);
    int TMax = ~TMin;

    int x = TMin;
    int y = TMin;
    printf("%.8X\t%.8X\n", saturating_add(x, y), x + y);
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13

7FFFFFFF        00000000
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-wejh032g.xpe" 1>"/tmp/Microsoft-MIEngine-Out-bc3qbt2m.usi"
root@DAT:/mnt/d/desktop/documents/code/labs# 


80000000        FFFFFFFE
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-ka51v5z5.rm2" 1>"/tmp/Microsoft-MIEngine-Out-kxtkcnid.5pc"
root@DAT:/mnt/d/desktop/documents/code/labs# 

00114514        00114514
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-rv4pltwy.avz" 1>"/tmp/Microsoft-MIEngine-Out-4izedy3s.ebo"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.74

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/* Determine whether arguments can be subtracted without overflow */
int tsub_ok(int x, int y);

// 如果x-y不溢出，就返回1
int tsub_ok(int x, int y){
    int w = sizeof(x) << 3;
    //x > 0, y < 0 但 x - y < 0
    //x < 0, y > 0 但 x - y > 0
    int res = x - y;
  
    int s1 = !(x >> (w - 1)) && (y >> (w - 1)) && ((x - y) >> (w - 1));
    int s2 = (x >> (w - 1)) && !(y >> (w - 1)) && !((x - y) >> (w - 1));

    return !(s1 || s2);
}

int main(void) {
    int w = sizeof(int) << 3;
    int TMin = 0x1 << (w - 1);
    int TMax = ~TMin;

    int x = TMin;
    int y = TMax;
    printf("%d\n", tsub_ok(x, y));

    return 0;
}

结果

1
2
3
4
5
6
7
8
9
0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-0x2x4bkt.lfp" 1>"/tmp/Microsoft-MIEngine-Out-3zcqdw5f.4if"
root@DAT:/mnt/d/desktop/documents/code/labs# 


1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-jiujtxao.1s0" 1>"/tmp/Microsoft-MIEngine-Out-2yebfsly.kkm"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.75 *

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <inttypes.h>


/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

unsigned unsigned_high_prod(unsigned x, unsigned y){
    int w = sizeof(unsigned) << 3;

    /**
     * 
     * B2U - B2T = x(w-1)2^w
     * B2U = B2T + x(w-1)2^w
     * B2U(T2B) = T2U = x + x(w-1)2^w  其实就是对于原本有符号数的x，补上最高位负权位(w-1)的数字，然后就是无符号数了。
     * U_x * U_y =  (x + x(w-1)2^w) * (y + y(w-1)2^w) = x * y + x * y(w-1)2^w + y * x(w-1)2^w +  x(w-1)2^w * y(w-1)2^w
     * 如果是对于高位，x * y就是原本的signed_high_prod
    */

   //转换成int类型，不要用x = (int)x; 因为x被声明为unsigned，即使转换成int，最后赋值还是会被隐式的转换成unsigned！
    int a = x;
    int b = y;
    //为了防止算数右移带来的高位置1，这里先转成unsigned，让他用逻辑右移
    unsigned h_x = (unsigned)a >> (w - 1);
    unsigned h_y = (unsigned)b >> (w - 1);
  
    //记得先转成64位的
    int64_t temp = (int64_t)a * b;
    //然后按照公式算就行
    return (temp >> 32) + a * h_y + b * h_x + h_x * h_y;
}


int main(void) {
    int x = 0xFF123;
    int y = 0xFF845678;
    printf("%.8X\t%.8X\n", unsigned_high_prod(x, y), x * y);
    return 0;
}

结果

1
2
3
4
000FE96F        9586CA68
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-qb4t0rys.lol" 1>"/tmp/Microsoft-MIEngine-Out-qd5swdqq.p05"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

难点主要在对公式的理解和注意一些类型转换的细节，尤其是对于x = (int)x; 如果x一开始被声明为unsigned，即使转换成int，最后赋值还是会被隐式的转换成unsigned！

2.76

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

void *calloc(size_t nmemb, size_t size){
    //如果nmemb或者size为0，返回NULL
    __uint64_t is_0 =~(!(nmemb && size)) + 1;
    void *mem;
    //分配空间
    mem = malloc(size * nmemb);
    memset(mem, 0, sizeof(mem));

    return (void *)((__uint64_t)NULL & is_0 | (__uint64_t)mem & ~is_0);  
}

int main(void) {
    int *test;
    test = (int *)calloc(13, 8);
    printf("%d\n", *(test + (2 * 12)));
    return 0;
}

结果

1
2
3
4
5
6
7
134401
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-mxey4y2v.nhh" 1>"/tmp/Microsoft-MIEngine-Out-fb0oejud.hue"
root@DAT:/mnt/d/desktop/documents/code/labs# 

0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-04ownrie.31m" 1>"/tmp/Microsoft-MIEngine-Out-55kqzgh0.dv5"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.77

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/


int main(void) {
    //只能用+、-、<<
    int x = 1;

    //K = 17, 17 = 16 + 1
    int A = (x << 4) + (x << 0);
    printf("%d\n", A);

    //K = -7, -7 = 0 - 7 = 0 - (4 + 2 + 1)
    int B = 0 - ((x << 2) + (x << 1) + (x << 0));
    printf("%d\n", B);

    //K = 60, 60 = 32 + 16 + 8 + 4
    int C = (x << 5) + (x << 4) + (x << 3) + (x << 2);
    printf("%d\n", C);

    //K = -112, -112 = 0 - 112 = 0 - (64 + 32 + 16)
    int D = 0 - ((x << 6) + (x << 5) + (x << 4));
    printf("%d\n", D);

    return 0;
}

结果

1
2
3
4
5
6
7

17
-7
60
-112
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-taoyye15.mf0" 1>"/tmp/Microsoft-MIEngine-Out-adpir0se.xsv"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.78

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

/* Divide by power of 2. Assume 0 <= k < w-1 */
int divide_power2(int x, int k);

// 要用正确的舍入计算x/2^k，使用向0舍入。
int divide_power2(int x, int k){
    /**
     * 向0舍入也就是正数向下舍入，负数向上舍入。
     * 我们可以把显示位记为X,被向右移出的位记为Y。也就是XY.0右移一定次数后变成了SX.Y。其中S代表算数右移填充的0或者1
     * 对于正数，因为XY部分最后计算是>=0的，所以舍去Y(也是>=0的)，最后会偏小，也就是向下舍入。
     * 对于负数，因为XY部分最后计算是<0的，所以舍去Y(>=0)，最后也会导致整体偏小，依旧是向下舍入。
     * 所以对于负数，要在算数右移之前加一个偏置，让负数可以正确的向上舍入
     * 加的这个偏置要让SX + 1，所以在低k位的Y加上一个k位的全1数字就可以保证高w-k位的SX一定会+1
     * 
    */
    int w = sizeof(int) << 3;
    //设置负数的掩码
    int mask = (x >> (w - 1));
    int bias = (1 << k) - 1; 
    //如果是负数就加偏置，否则就不加
    return ((x + bias) >> k) & mask | (x >> k) & ~mask;
}
int main(void) {
    int x = -12340;
    int k = 4;
    int temp = divide_power2(x, k);
    printf("%d\n",temp);
    return 0;
}

结果

1
2
3
4
5
6
7
771
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-ke4pq1t0.0qt" 1>"/tmp/Microsoft-MIEngine-Out-enlx00jk.1ba"
root@DAT:/mnt/d/desktop/documents/code/labs# 

-771
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-dowxttdb.sdr" 1>"/tmp/Microsoft-MIEngine-Out-it2rzfpx.beq"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.79

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int mul3div4(int x);

int mul3div4(int x){
    //3*x/4 先乘后除
    int mul3 = x * 3;
    int w = sizeof(int) << 3;

    int mask = (x >> (w - 1));

    int k = 2;
    int bias = (0x1 << k) - 1;

    return mask & ((mul3 + bias) >> k) | ~mask & (mul3 >> k);
}

int main(void) {
    int x = ~(0x1 << 31);
    printf("%d\n", mul3div4(x));
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
536870911
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-kptkseci.w0p" 1>"/tmp/Microsoft-MIEngine-Out-ehrr5aaa.0hk"
root@DAT:/mnt/d/desktop/documents/code/labs# 

-22
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-eriflhry.nje" 1>"/tmp/Microsoft-MIEngine-Out-uuuo0qrd.hrh"
root@DAT:/mnt/d/desktop/documents/code/labs# 

22
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-3omo23m5.s35" 1>"/tmp/Microsoft-MIEngine-Out-cjvyzfpz.pwl"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.80 *

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/
int threefourths(int x);

// 计算(3/4)x
int threefourths(int x){
    int w = sizeof(int) << 3;
    //必须先计算3x，否则3/4会被直接舍为0，但是对于3x要确保不会溢出。
    //可以将3x分为高低位，
    int k = 2;

    //获取高位和低位
    __int64_t mul3_l = (__int64_t)x * 3;
    int mul3_h = mul3_l >> 32;

    //然后将高位的最低两位移到低位的最高位。
    //不过首先，还是先判断是不是负数，先对对负数加上偏置
    __int64_t mask = mul3_h >> (w - 1); //对于负数，如果转换为更多字节的类型，会自动在高位补1
    int bias = (1 << k) - 1;
    mul3_l = mask & (mul3_l + bias) | ~mask & mul3_l;

    //将整个数右移2位
    return mul3_l >> k;
}

int main(void) {
    int test = 0x80000000;
    printf("res : %.8X\t\toriginal : %.8X\n", threefourths(test), test);
    printf("res : %d\toriginal : %d\n", threefourths(test), test);
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
res : A0000000          original : 80000000
res : -1610612736       original : -2147483648
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-kmnlfk1i.qk0" 1>"/tmp/Microsoft-MIEngine-Out-mi0h5hl5.3wc"
root@DAT:/mnt/d/desktop/documents/code/labs# 

res : 5FFFFFFF          original : 7FFFFFFF
res : 1610612735        original : 2147483647
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-cczlcbn1.mpj" 1>"/tmp/Microsoft-MIEngine-Out-tv1lvxuj.5vz"


res : 00000003          original : 00000004
res : 3 original : 4
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-aqc05wrx.iuz" 1>"/tmp/Microsoft-MIEngine-Out-1b5iseia.my2"
root@DAT:/mnt/d/desktop/documents/code/labs# 


res : 00014F7D          original : 0001BF52
res : 85885     original : 114514
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-z410jtc0.5sf" 1>"/tmp/Microsoft-MIEngine-Out-dt0bwvrh.coc"
root@DAT:/mnt/d/desktop/documents/code/labs# 


res : FFFEB083          original : FFFE40AE
res : -85885    original : -114514
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-xucxooza.d5d" 1>"/tmp/Microsoft-MIEngine-Out-m3c2bck2.bv1"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

难点主要是对溢出的情况的处理，同时加上偏置的时候，也要考虑高位进位的情况。不过之前已经做过了高位溢出的练习了，所以这一题不算特别费劲。

2.81

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int main(void) {
    //A.前w-k位是1，后k位是0
    //B.前w-k-j位是0，中间k位是1，最后j位是0
    //不让用w

    int k, j;
    k = 28, j = 4;
    //A.可以将1左移k位，然后1后面跟着k个0，然后减1，获得低k位全1
    int A = (0x1 << k) - 0x1;
    printf("%.8X\n", A);

    //B.先让低k+j位全1，然后减去低j位全1，就可以得到中间k位1但是低j位0的数字
    int B = (0x1 << (k + j)) - 0x1;
    int B_j = (0x1 << j) - 0x1;

    //对于k+j = w的情况，需要另外讨论。这时B = 0，应该让B = -1
    int mask = ~(~(!!B) + 1);
    B = mask & ~(0x0) | ~mask & B;

    B = B - B_j;
    printf("%.8X\n", B);
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

0FFFFFFF
FFFFFFF0
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-s2xc0rzh.ifs" 1>"/tmp/Microsoft-MIEngine-Out-icjflp3b.1kc"
root@DAT:/mnt/d/desktop/documents/code/labs# 


0000003F
000001F8
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-gjyls33c.3io" 1>"/tmp/Microsoft-MIEngine-Out-4cd2pz2v.xlq"
root@DAT:/mnt/d/desktop/documents/code/labs# 

0000000F
F0000000
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-2fjqzwed.jme" 1>"/tmp/Microsoft-MIEngine-Out-rub5222f.puu"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

对于想获取低k位全1的情况，也不要总想着利用算数右移的特点来取反获取，也可以利用对2^k减去1嘛

2.82

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int main(void) {
    /* Create some arbitrary values */
    int x, y;
    /* Convert to unsigned */
    unsigned ux = (unsigned) x;
    unsigned uy = (unsigned) y;

    //A.(x<y)==(-x>-y) -> 0
    //-x == ~x + 1。但是如果x是TMin(0x80000000),~TMin == 0xEFFFFFF，~TMin + 0x1 == 0x8000000。导致x在不为0的情况下-x == x。
    int w = sizeof(int) << 3;
    x = 0x80000000;
    y = 100;
    int A = (x < y) == (-x) < (-y);
    printf("A.\t%d\n", A); //不能用-x > -y,不然因为优先级问题会导致结果非预期

    //B.((x+y)<<4)+y-x==17*y+14*x -> 1
    //总是为1，对于溢出的情况最后计算的结果依旧一致
    x = 0x7FFFFFFF;
    y = 0x7FFFFFFF;
    int B = ((x + y) << 4) + y - x == 17 * y + 15 * x;
    printf("B.\t%d\n", B);

    //C.~x+~y+1==~(x+y) -> 1
    x = 0x80000000;
    y = 0x7FFFFFFF;
    int C = (~x) + (~y) + 1 == ~(x + y);
    printf("C.\t%d\n", C);

    //D.(ux-uy)==-(unsigned)(y-x) -> 1
    //因为对于(unsigend)(y - x)最后计算的结果也是和int结果位模式一致的unsigned。
    x = -1;
    y = 0x7FFFFFFF;
    ux = (unsigned) x;
    uy = (unsigned) y;
    int D = (ux - uy) == -(unsigned)(y - x);
    printf("D.\t%d\n", D);


    //E.((x>>2)<<2)<=x -> 1
    //对于正数，左侧的低两位信息丢失，最后肯定是<=原本的x的
    //对于负数，左侧的地两位信息丢失导致负权占比有可能更大，所以最后还是更小了，所以还是<=x
    int E = ((x >> 2 ) << 2) <= x;
    printf("E.\t%d\n", E);
    return 0;
}

结果

见code

2.83

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int main(void) {
    //A. Y = B2U(y)  string = Y >> k

    //B.
    //(a)101
    int base = 100000000;
    int Y = (base >> 1) + (base >> 3);
    printf("0.%d\n", Y);

    //(b)0110
    Y = (base >> 2) + (base >> 3);
    printf("0.%d\n", Y);

    //(c)010011
    Y = (base >> 2) + (base >> 5) + (base >> 6);
    printf("0.%d\n", Y);

    return 0;
}

结果

1
2
3
4
5
6

0.62500000
0.37500000
0.29687500
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-n5z5htq5.ffo" 1>"/tmp/Microsoft-MIEngine-Out-ri0iwva5.umk"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.84

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

unsigned f2u(float x){
    return (unsigned)x;
}

//x是否小于等于y
int float_le(float x, float y){
    unsigned ux = f2u(x);
    unsigned uy = f2u(y);

    /* Get the sign bits */
    unsigned sx = ux >> 31;
    unsigned sy = uy >> 31;

    /* Give an expression using only ux, uy, sx, and sy */
    // 对于异号，只有当sx为1，且sy为0时满足
    // 对于同号，则计算uy - ux，看其符号位是不是0。如果是0则代表，y > x 或者 y == x。
    return (sx && !sy) || !(sx ^ sy) && !((uy + ~ux + 1) >> 31);
}
int main(void) {
  
    float x = 0;
    float y = -0;
    int f = float_le(x, y);
    printf("%d\t%d\t%d\n",f, (x <= y), f == (x <= y));
    return 0;
}

结果

1
2
3
4
5
6

1       1       1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-m00f15ie.0ua" 1>"/tmp/Microsoft-MIEngine-Out-gklbvvle.ola"
root@DAT:/mnt/d/desktop/documents/code/labs#


2.84

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

// 通过联合，将同一个内存地址中的内容用不同形式表达出来
unsigned f2u(float x){
    union{
        float f;
        unsigned u;
    }   conver;
    conver.f = x;

    return conver.u;
}

//x是否小于等于y
int float_le(float x, float y){
    unsigned ux = f2u(x);
    unsigned uy = f2u(y);

    /* Get the sign bits */
    unsigned sx = ux >> 31;
    unsigned sy = uy >> 31;

    //对于单精度浮点数，1位符号位s  8位阶码exp  23位尾数f
    //对于双精度浮点数, 1位符号位s  11位阶码exp 51位尾数f
    //对于单精度浮点数，根据exp，编码值分为三种
    //1. 规格化的： exp != 0  && exp != 255
    //2. 非规格化的: exp == 00000000    0
    //3. 无穷大:    exp == 11111111 && f == 0000....0000
    //4. NaN:      exp == 11111111 && f != 0
    //exp: E = exp - bias （规格化） E = 1 - bias （非规格化）; bias = (1 << (k - 1)) - 1 (对于单精度bias是127，双精度1023)
    //E对于单精度-126 ~ + 127   对于双精度 -1022 ~ +1023
    // M = 1 + f;
    // E = exp - bias
    // V = ((-1) ^ s) × M × (2 ^ E)



 
    /* Give an expression using only ux, uy, sx, and sy */
    //如果都是0，直接返回1

    //如果x负，y正，直接返回1；

    //如果x，y同正，那么ux <= uy，也就是uy - ux 符号位为0

    //如果x，y同负，那么ux >= uy，也就是ux - uy 符号位为0

    return (!((ux << 1) - 0x0) && !((uy << 1) - 0x0)) || 
            (sx & !sy) || 
            ((!sx && !sy) && !((uy + ~ux + 1) >> 31)) || 
            ((sx && sy) && !((ux + ~uy + 1) >> 31));





    //下面是之前花了大半天想出的错误答案，错误的原因是没有正确的理解exp的位表达。E的正负是利用e-bias计算得到，之前混淆了e和E的区别
    //虽然我确实明确知道e的范围是1~254，但是因为掌握不够深刻，导致我混淆了高位的exp和E的可负性，我以为exp的最高位就是符号位，这种简单
    //的小错误一直在我脑海深处，让我以为不能简单的比较符号位以下的数字大小来判断浮点数。就是这种迷迷糊糊的感觉最可怕，虽然实际行为是正确的符合理论的，
    //但是脑子里思考的一直是错误的。
    //哎，不过好在我改过来了，而且我认为不叫浪费时间
    //毕竟我通过这个错误将浮点数的逻辑通过代码实践了一番，理解更加深刻了。

    int is_same_p = !sx && !sy;
    int is_same_n = sx && sy;
    int s = (sx && !sy);
    int bias = 127;
    int mask_e = 0x7F800000; // 0111 1111 1000 .... 0000 
    int mask_f = 0x007FFFFF; // 0000 0000 0111 .... 1111
    int base_F = 0x00800000; // 0000 0000 1000 .... 0000

    int f_x = mask_f & ux;
    int e_x = (mask_e & ux) >> 23;
    int E_x = e_x - bias;
    int mask_e_s_x = E_x >> 31;
    f_x += base_F;
    // 就这一段很滑稽，明明我潜意识认为e_x是有符号的，但是我还是利用它来计算E_x，并且最后依靠的是E_x的正负形来操作小数位f。脑子真神奇。
    int F_x = (mask_e_s_x & (f_x >> (~E_x + 1)) | ~mask_e_s_x & (f_x << E_x));
    printf("f_x:%.8X\n", f_x);  
    printf("F_x:%.8X\n", F_x);
    printf("E_x:%d\n", E_x);
    printf("mask_e_s_x:%d\n\n", mask_e_s_x);

    int f_y = mask_f & uy;
    int e_y = (mask_e & uy) >> 23;
    int E_y = e_y - bias;
    int mask_e_s_y = E_y >> 31;
    f_y += base_F;
    int F_y = (mask_e_s_y & (f_y >> (~E_y + 1)) | ~mask_e_s_y & (f_y << E_y));
    printf("f_y:%.8X\n", f_y);  
    printf("F_y:%.8X\n", F_y);
    printf("E_y:%d\n", E_y);
    printf("mask_e_s_y:%d\n\n", mask_e_s_y);


    int res = !((F_y + ~F_x + 1) >> 31);
    int ress = is_same_n && !res || is_same_p && res || !(F_y + ~F_x + 1);
    printf("res:%d\n", res);

    //如果y<0且x>0，则直接返回0。否则继续讨论
    //如果y>0且x<0，就返回1
    //ress是对小数位比较
    // return !(!sx && sy) && (s || ress);
}
int main(void) {

    float x = 3.9E40;
    float y = 3.8E40;
  
    // printf("%.8X\t%.8X\t%f\n", conver.u, conver.i, conver.f);
    int res = float_le(x, y);

    // printf("%d\t%d\t%d\n", res, (x <= y), res == (x <= y));


    //     union{
    //     float f;
    //     unsigned u;
    //     int i;
    // }   conver;
    // conver.f = x;

    // printf("%.8X\t%.8X\t%f\n", conver.u, conver.i, conver.f);
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

res:1
1       1       1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-2wdtkdot.g4r" 1>"/tmp/Microsoft-MIEngine-Out-pdamq2ig.qmz"
root@DAT:/mnt/d/desktop/documents/code/labs# 


0       0       1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-5voazk52.jpm" 1>"/tmp/Microsoft-MIEngine-Out-ds2inloh.og1"
root@DAT:/mnt/d/desktop/documents/code/labs# 


1       1       1
[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-2th5ba1h.1q0" 1>"/tmp/Microsoft-MIEngine-Out-ziafcqeo.tdl"
root@DAT:/mnt/d/desktop/documents/code/labs#

总结

说实话，虽然中间磕磕碰碰，而且方法还用错了，为了这一道题花了特别多时间，但是学到了很多东西，所以值得！倒不如说，这道题补齐了我浮点数理解不够深入的短板。感谢我的错误理解，让我直接从零开始尝试复现浮点数计算的底层逻辑。

2.85

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int main(void) {
    union {
        float f;
        unsigned u;
    } conver_32;

    union{
        double d;
        unsigned long int lu;
    } conver_64;
  
    //有k位指数和n位小数。写出阶码E、尾数M、小数f和值V
    //则exp有k位，bias有2^(k - 1) + 1位 ， f有n - k - 1 位
    /**
     * A. 数字7.0
     * 7.0 == 111.000 == 1.11000 × 2^2
     * E = 2, f = 110000000... , M = 1.1100...., V = 111.00... = 7.00...
     * 
    */
   //对于float就是k = 8, n = 32
   //s = 0
   //exp = 127 + 2 = 129 = 1000 0001
   //f = 1100 0000 ....
   //V = 0100 0000 1110 0000 .... 0000 = 0x40E00000
   puts("A.");
   conver_32.u  = 0x40E00000;
   printf("float:\t%f\n", conver_32.f);
    //对于double就是k = 11, n = 64。 切记，k是11，不是12或者其他！！
    //s = 0
    //exp = 1023 + 2 = 1025 = 100 0000 0001
    //f = 1100 0000 ....
    //V = 0100 0000 0001 1100 0000 .... 0000 = 0x401C000000000000
    conver_64.lu = 0x401C000000000000;
   printf("double:\t%lf\n\n", conver_64.d);

   /**
    * B.能够被描述的最大奇整数。
    * 当小数位f被完全表达时同时是最大的整数。
    * f应该类似 f = 1111 .... 1111。
    * 然后对于E，不能超过2^(k - 1) + 1，因为exp最大不能超过2^k - 1。
    * 但是超出尾数部分，最后补0，会导致最后始终都是偶数，所以必须确保最低位必须是1，所以E必须是n - k - 1
    * exp = E + Bias = n - k - 1 + 2^(k - 1) + 1, M = 1。
    * M = 1.1111111 × 2^(n - k - 1)
    * V = 2^(n - k - 1) × 1.11111... × 1
   */
   //对于float就是k = 8，n = 32
   //f长23位，E = 23
   //s = 0
   //exp = 23 + 127 = 150 = 1001 0110
   //M = 1.111.... × 2^(23)
   //f = 1111 1111 .... 1111
   //V = 0100 1011 0111 1111 .... 1111 = 0x4B7FFFFF
   puts("B.");
   conver_32.u = 0x4B7FFFFF;
   printf("float:\t%f\n", conver_32.f);
   //对于double就是k = 11，n = 64
   //f长52位，E = 52
   //s = 0
   //exp = 52 + 1023 = 1075 = 100 0011 0011
   //f = 1111 1111 .... 1111
   //V = 0100 0011 0011 1111 .... 1111 = 0x433FFFFFFFFFFFFF
   conver_64.lu = 0x433FFFFFFFFFFFFF;
   printf("double:\t%lf\n\n", conver_64.d);
    /**
     * 最小规格化数应该就是负数最小值把
     * 然后对于倒数的话，把E从最大值调到最小值
     * s = 1
     * exp = 1 = 0000 0001
     * M = 1.111....
     * f = 1111 1111 .... 1111
     * V = 1000 0000 1111 1111 .... 1111 = 0x80FFFFFF
    */
   puts("C.");
   conver_32.u = 0x80FFFFFF;
    printf("float:\t%.170f\n", conver_32.f);
    /**
     * s = 1
     * exp = 1 = 000 0000 0001
     * M = 1.111....
     * f = 1111 1111 .... 1111
     * V = 1000 0000 0001 1111 .... 1111 = 0x801FFFFFFFFFFFFF
    */
   conver_64.lu = 0x800FFFFFFFFFFFFF;
   printf("double:\t%.1100lf\n\n", conver_64.d);

    return 0;
}

结论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

A.
float:  7.000000
double: 7.000000

B.
float:  16777215.000000
double: 9007199254740991.000000

C.
float:  -0.00000000000000000000000000000000000002350988561514728583455765982071533026645717985517980855365926236850006129930346077117064851336181163787841796875000000000000000000000
double: -0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002225073858507200889024586876085859887650423112240959465493524802562440009228235695178775888803759155264230978095043431208587738715835729182199302029437922422355981982750124204178896957131179108226104397197960400045489739193807919893608152561311337614984204327175103362739154978273159414382813627511383860409424946494228631669542910508020181592664213499660651780309507591305871984642390606863710200510872328278467884363194451586613504122347901479236958520832159762106637540161373658304419360371477835530668283453563400507407304013560296804637591858316312422452159926254649430083685186171942241764645513713542013221703137049658321015465406803539741790602258950302350193751977303094576317321085250729930508976158251915972075723245543477091246131749358028173446655273437500000000000000000000000000

[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-fvtdzsil.3xf" 1>"/tmp/Microsoft-MIEngine-Out-4uxmzyh4.oz2"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.89

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>



/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

int main(void) {
    union{
        float f;
        int i;
    }   conver_32;
    union{
        double d;
        int i;
    }   conver_64;
  

    int x, y, z;

    x = 0x80000000;
    y = 0x7FFFFFFF;
    z = 0;
    double dx = (double)x;
    double dy = (double)y;
    double dz = (double)z;

    //判断四个等式是否总是为1

    //A.(float)x == (float)dx -> 1 
    conver_32.f = (float)dx;
    printf("%.8X\t%.8X\n",x, conver_32.i);
    printf("%f\t%f\n",(float)x, (float)dx);
    printf("A.\t%d\n\n",(float)x == (float)dx);

    //B.dx-dy==(double)(x-y) -> 0
    //如：    x = 0x80000000;
    //        y = 0x7FFFFFFF;
    //对于整形减法x - y，可能导致溢出的情况时，x - y会先计算溢出后错误的int值，然后再转换成double，
    //而对于双精度浮点数减法dx - dy可能则不会引起溢出，最后导致两者结果不一致。
    printf("B.\t%d\n\n",(dx-dy) == (double)(x-y));

    //C.(dx+dy)+dz == dx+(dy+dz) -> 1
    //虽然对于浮点数加法在精度相差过大的两数之间运算会导致舍入，导致浮点数加法的不可结合性。
    //但是对于int型转变的双精度浮点数来说，还不会导致这种现象的发生。
    printf("C.\t%d\n\n",((dx+dy)+dz) == (dx+(dy+dz)));

    //D.(dx*dy)*dz==dx*(dy*dz) -> 1
    //虽然对于浮点数乘法由于溢出问题也不具有普遍意义上的结合性
    //但是对于int型转变的double来说，还不足以导致这种现象
    printf("D.\t%d\n\n",((dx*dy)*dz) == (dx*(dy*dz)));

    //E.dx/dx==dz/dz -> 0
    //很显然，当dx或者dz为0时，等式不成立
    printf("E.\t%d\n\n",(dx/dx)==(dz/dz));
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13

A.      1

B.      0

C.      1

D.      1

E.      0

[1] + Done                       "/usr/bin/gdb" --interpreter=mi /usr/bin/gdb --tty=${DbgTerm} 0<"/tmp/Microsoft-MIEngine-In-bvclesk0.y5s" 1>"/tmp/Microsoft-MIEngine-Out-coxfxidg.wcq"
root@DAT:/mnt/d/desktop/documents/code/labs#

2.90

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <math.h>


/* 1.禁止使用：
*	所有条件(包括?:)、循环、分支、语句，函数调用和宏调用。
*	除法、模运算、和乘法。
*  相对比较运算(>, <, >=, <=)。
*  2.允许的运算：
*  所有的位级和逻辑运算。
*  左移和右移，但是位移量只能在0和w - 1之间。
*  加法和减法。
*  相等和不相等测试。（有一些题目中，也不允许这些运算。）
*  INT_MIN和INT_MAX。
*  对int和unsigned的强制类型转换，无论显式的还是隐式的。
*/

float u2f(unsigned uf);

float fpwr2(int x){
    /* Result exponent and fraction */
    unsigned exp, frac;
    unsigned u;

    // E =-126 - 23 = -149 把1移到f的最低位就是极限了
    if(x < -149){
        /* Too small. Return 0.0 */
        exp = 0;
        frac = 0;
    }
    else if(x < -126){
        /* Denormalized result */
        //对于非规范数字，e的公式变成了1 - bias，e始终0
        exp = 0x0;
        //而对于f，则是1从最高位移到最低位的23种情况
        frac = 1 << (23 - (-x - 126));
        printf("%.8X\n", frac);
    }
    else if(x < 128){
        /* Normalized result */
        exp = x + 127;
        frac = 0;
    }
    else{
        /* Too big, return +infinity*/
        exp = 255;
        frac = 0;
    }

    /* Pack exp and frac into 32 bits */
    u = exp << 23 | frac;
    /* Return as float */
    return u2f(u);
}

float u2f(unsigned uf){
    union{
        float f;
        unsigned u;
    } conver;
    conver.u = uf;

    return conver.f;
}
int main(void) {
    union{
        float f;
        unsigned u;
    } conver;

    union{
        float f1;
        unsigned u1;
    } conver1;

    int x = -149;
    float a = pow(2,x);
    float b = fpwr2(x);
    conver.f = a;
    conver1.f1 = b;
    printf("%.200f\n%.200f\n\n", a, b);
    printf("%.8X\n%.8X\n", conver.u, conver1.u1);
    return 0;
}

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# ./2_90
0.00000000000000000000000000000000000000000000140129846432481707092372958328991613128026194187651577175706828388979108268586060148663818836212158203125000000000000000000000000000000000000000000000000000
0.00000000000000000000000000000000000000000000140129846432481707092372958328991613128026194187651577175706828388979108268586060148663818836212158203125000000000000000000000000000000000000000000000000000

00000001
00000001
root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# 

root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# ./2_90
0.00000000000000000000000000000000000001175494350822287507968736537222245677818665556772087521508751706278417259454727172851562500000000000000000000000000000000000000000000000000000000000000000000000000
0.00000000000000000000000000000000000001175494350822287507968736537222245677818665556772087521508751706278417259454727172851562500000000000000000000000000000000000000000000000000000000000000000000000000

00800000
00800000
root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# 

root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# ./2_90
1.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

3F800000
3F800000

root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# ./2_90
170141183460469231731687303715884105728.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
170141183460469231731687303715884105728.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

7F000000
7F000000
root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# 

root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework# ./2_90
inf
inf

7F800000
7F800000
root@DAT:/mnt/d/desktop/documents/code/labs/csapplab/2_homework#

总结

这题还是很有趣的，需要认真考虑规范数和非规范数边界地方的细节。同时也更深刻理解了规范数和非规范数的区别，明白了非规范数字只是因为没办法用指数来控制所以“非规范”，并不代表非规范数都不是数。而且这次的工作其实就相当于纯手撸了一个pow(2, x)。
了解了底层原理之后，说不定可以手撸一个pow_double(2, x)呢，精度比单纯的pow(2, x)更高的那种。