前言

实验文档与代码框架

本文档是参照笔者在sp25所选的西安交通大学计算机系统导论课程与配套实验内容而写成的，参考教材就是大名鼎鼎的CSAPP。至今课程网站仍然可以访问（如果不是校园网连接，可能需要科学上网技术），实验文档、课程PPT、部分代码框架也均可以在上面找到。有兴趣的读者可以自行了解更多内容。

实验1的代码框架是一致的，都可以从这一仓库获取，直接git clone即可。

默认前提

本文默认读者已经掌握以下知识/技巧：

  • 能够熟练地掌握C语言的基本语法；
  • 有较好的数据结构知识基础；
  • 能够较为熟练地使用Git、make等工具链；
  • 对Linux命令行的基本操作较为熟悉。

但是如果你此时仍然没有掌握以上提到的基本知识，那也没有关系，不会影响完成这个实验。但是为了更好地了解你的电脑，便利你此后的学习之路，你可以尝试学习一下MIT的课程The Missing Semester of Your CS Education，或者直接开始，在必要的时候耐心地向各家LLM求助。我个人更为推荐第二种方法，因为我也是这样一步一步地走过来的，虽然这是野路子，但是它能让你跳过打基础的boredom，直接上手做一些直击目标的工作，从而不至于让你很快对计算机丧失兴趣。

原则

  • 如果你是一名正在选修ICS的XJTU的学生，请你务必首先尝试独立解决课程的所有实验，如果实在觉得想不出来了，再参考本文档的解法；非选课人士也可以参考此文档与代码框架，尝试自己完成这些实验。
  • 我会记录下我本次解题过程中联想到的某些知识点，有些和实验内容有关，有些关系不大，但是值得一看。

参考实现

本人的实验代码会同步到这一仓库，读者可以自行拉取到本地参考。但是，请一定要阅读仓库的README文件，坚持独立完成实验，不要抄袭。独立完成实验对于你的实际能力提升有很大帮助。

实验内容

基本任务

这个实验给出了10个小谜题，规定你需要使用尽可能少的基础逻辑运算符来实现各种逻辑/算术操作。每一题对操作符的数量都有严格限制，能够使用的运算符种类也很有限，基本上就是数字逻辑电路中讲到的最基础的逻辑门。

实验要求

这10个谜题实际上就是10个函数，分别描述了十种常见的逻辑或算术运算的操作。每个函数中，必须遵循以下要求：

  • 使用的运算符个数不能多于每个题目中给出的数字，这个数字会在每道题的注释中的Max ops中给出；

  • 只能使用整数，且只能使用int数据类型，可以设定的值范围为0到255(0xFF)；不能使用强制类型转换；

  • 总体上，只能使用以下操作符：

    • 一元操作符：! ~
    • 二元操作符：& ^ | + << >>

    事实上，每道题都在以上可用符号范围内做了更严格的筛选，可用的符号在注释的Legal ops字段中给出。

  • 每个题的参数/变量都只能在函数内设定，不能用全局变量；

  • 不能使用任何的控制字段，如if do + while while for switch等；

  • 不能使用宏定义，不能定义额外函数，不能包含其他的库，不能调用其他函数；

  • 不能使用数组/结构体/联合体

题目展示

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
// Rating 1
/*
 * isZero - returns 1 if x == 0, and 0 otherwise 
 *   Examples: isZero(5) = 0, isZero(0) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int isZero(int x) {
  return !x;
}
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return 2;
}
// Rating 2
/* 
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x) {
  return 2;
}
/* 
 * isNegative(x) - return 1 if x < 0, return 0 otherwise 
 *   Example: isNegative(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNegative(int x) {
  return 2;
}
/* 
 * allEvenBits - return 1 if all even-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allEvenBits(int x) {
  return 2;
}
/* 
 * byteSwap - swaps the nth byte and the mth byte
 *  Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
 *            byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
 *  You may assume that 0 <= n <= 3, 0 <= m <= 3
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 25
 *  Rating: 2
 */
int byteSwap(int x, int n, int m) {
    return 2;
}
/* 
 * removeRightmostOne(x) - remove the rightmost 1 from x
 *   Example: removeRightOne(0b0110) = 0b0100, removeRightOne(0b0101) = 0b0100, removeRightOne(0) = 0
 *   Legal ops: & ~ +
 *   Max ops: 10
 *   Rating: 2
 */
int removeRightmostOne(int x) {
    return 2;
}
// Rating 3
/*
 * maskBelowHighest(x) - set all bits below the highest bit set 
 *   Example: maskBelowHighest(0b01101011) -> 0b01111111
 *            maskBelowHighest(0b10000000) -> 0b11111111
 *            maskBelowHighest(0) -> 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int maskBelowHighest(int x)
{
    return 2;
}
/*
 * largerAbsVal - return the number who has a larger Abs. if |a| == |b|, return the first.
 *   Example: largerAbsVal(-5, 3) = -5, largerAbsVal(-1, 4) = 4
 *            largerAbsVal(-3, 3) = -3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3
 */
int largerAbsVal(int a, int b) {
  return 2;
}
// Rating 4
/*
 * bitReverse - Reverse bits in a 32-bit word
 *   Examples: bitReverse(0x80000002) = 0x40000001
 *             bitReverse(0x89ABCDEF) = 0xF7D3D591
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int bitReverse(int x) {
    return 2;
}

题解

isZero

1
2
3
4
5
6
7
8
9
10
/*
 * isZero - returns 1 if x == 0, and 0 otherwise 
 *   Examples: isZero(5) = 0, isZero(0) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int isZero(int x) {
	return 2;
}

由C语言的规范可知，单目运算符!与任何非0的数组合，结果都是0；与0结合，结果就是1 。所以说，按照这个定义，!x刚刚好就符合题目的要求，!就是做了一个判断是否为0的工作。答案为：

1
2
3
int isZero(int x) {
  return !x;
}

bitXor

1
2
3
4
5
6
7
8
9
10
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
	return 2;
}

这道题要求实现按位异或的操作，比如例子中，4对应的二进制表示是0100，5对应的是0101，按位异或后就是0001，也就是1 。

如果你学过数电，你可能会想，这太简单了，直接画一个卡诺图，写一下异或的表达式不就好了？

由于x⊕y=x‾y+y‾xx\oplus y=\overline x y+\overline yx，因此你可能会写出以下的式子：

1
2
3
int bitXor(int x, int y) {
   return ((~x) & y) | ((~y) & x);
}

好像很简单是不是？但是问题在于，题目中不让使用|这个运算符！所以那怎么办？

这时你想到了，逻辑代数中还有一个很重要的定律，就是所谓德摩根律，可以巧妙地规避对|的使用。所以变换后式子为x⊕y=x‾y+y‾x=x‾y‾ y‾x‾‾x\oplus y=\overline xy +\overline yx=\overline{\overline{\overline xy} \, \overline{\overline yx} }，这下一切都解决了。于是写出来：

1
2
3
int bitXor(int x, int y) {
   return ~(~((~x) & y) & ~((~y) & x));
}

总共用到了8个符号，没有问题。

copyLSB

1
2
3
4
5
6
7
8
9
10
/* 
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x) {
	return 2;
}

这个题的的意思是说，将32个二进制位的值都设置成LSB的值，也就是最低位。从问题出发，我们可以分成两步来实现我们的目的：

  1. 获取最低位的值；
  2. 返回全部32位都是这个值的结果数。

所以先看第一步。注意到，一个二进制位x与1做与运算，结果一定是它自身；与0做与运算，结果恒为0。所以x & 1就能获取它的最低位。

第二步我们要把这一个位给拓展到全部的32位。这里有一点弯弯绕。你可能会想到用最低位向左不断复制，第一次复制1位，第二次复制2位，第三次复制4位，直到填满全部32位。但是这里对符号数的限制非常严，说明这样的思路走不通。所以该怎么办呢？

如果你刚好在复习移位运算，你可能会想到，算术右移和逻辑右移的规则。简单说：

  • 算术右移：右移时使用符号位填补空位；
  • 逻辑右移：右移时正常填0 。

所以，我们可以想办法把最低位放到最高位，然后再右移回来！

所以就有了以下的解法：

1
2
3
int copyLSB(int x) {
    return (x & 1) << 31 >> 31;
}

在写这篇文档的时候我也在重做这十道题，本来以为会很轻松，结果在这一道就卡住了，想了好长时间也没想起怎么做，最后看了一眼去年我自己交的文件才恍然大悟，不知道当初是想了多长时间想出来的。

isNegative

1
2
3
4
5
6
7
8
9
10
/* 
 * isNegative(x) - return 1 if x < 0, return 0 otherwise 
 *   Example: isNegative(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNegative(int x) {
	return 2;
}

有了上一题打基础，这一题就显得非常简单了。先将符号位移到LSB，然后用 “与1” 的操作来获取最低位，就是最终的答案。

1
2
3
int isNegative(int x) {
	return (x >> 31) & 1;
}

allEvenBits

1
2
3
4
5
6
7
8
9
10
11
/* 
 * allEvenBits - return 1 if all even-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allEvenBits(int x) {
	return 2;
}

这个题目的大意是，如果从低位到高位，所有索引为偶数的位都是1 ，则返回1；反之则返回0 。

从直觉出发，这个题可能是要用到移位的操作的，毕竟我们要统计不同位上的1的个数。但是如果将从第0位到第30位总共16位数字逐一移位再相与，那肯定会超出符号数限制；而为了减少符号数，我们可以利用一种类似二分的思想：每次将机器数总长度一分为二，将左半部分右移和右半部分相与，这样32位的数字逐一相与也只需要折叠5次。理论存在，开始实践：

1
2
3
4
5
6
7
8
9
10
int allEvenBits(int x) {
   int res;
   int sel = 0x55 + (0x55 << 8);
   sel = sel + (sel << 16);
   res = x & sel;
   res = (res >> 16) & res;
   res = (res >> 8) & res;
   res = (res >> 4) & res;
   return (res >> 2) & res;
}

敲完代码，仔细数数符号数……嗯？！怎么超了？好像也没什么优化的空间，这可怎么办？

我们需要新的方法。

注意到，既然是检验偶数位是否都是1 ，那我们构造一个偶数位全1 ，奇数位和原数一致的数，和原数比较一下不就好了？所以我们改造代码如下：

1
2
3
4
5
6
7
8
9
10
11
int allEvenBits(int x) {
   int res;
   int bitSel;
   int test;
   int isEqual;
   bitSel = 0x55 + (0x55 << 8);
   bitSel = bitSel + (bitSel << 16); 
   test = x | bitSel;
   isEqual = !(test ^ x);
   return isEqual;
}

test就是我们构造出来的数字，让它和x相比较，如果相等就是1 ，不相等就是 0 。!(x ^ y)就可以实现两数比较这个功能。

byteSwap

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * byteSwap - swaps the nth byte and the mth byte
 *  Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
 *            byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
 *  You may assume that 0 <= n <= 3, 0 <= m <= 3
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 25
 *  Rating: 2
 */
int byteSwap(int x, int n, int m) {
   return 2;
}

这个题给定一个原数x，两个字节索引n m，要求交换原数的第n和第m个字节上的数据。索引从低位字节开始，从低到高。

这道题本身的理解上没有什么问题，但是它让我想到了一个CSAPP和计算机组成原理中都涉及到的小知识点：大端序和小端序。

  • 大端序（Big-endian Order）：一个数据的低字节存储在内存地址空间的高处，比如0x12345678，0x78是最低的字节，然而在存储的时候却被放到内存地址最高的单元。所以在地址空间中存储的形式也是12 34 56 78（地址空间向右增长）。

  • 小端序（Little-endian Order）：数据的低字节存储在低地址，比如上面这个例子，存储的时候会变成这样：78 56 34 12。

大端序和小端序之所以能够出现，本质上还是因为计算机机器字长（计算机一次性能直接处理的二进制数据位数）的长度往往比内存编址的单位更大（虽然早期还有以存储字长为单位编址的，但是现在更多用字节），因此在一个字节内不能存下整个字长的数据，需要用一定的编址次序来存储。目前大部分计算机的存储字节序都选择小端序，比如Intel x86 ，以及大部分ARM处理器；而大端序在PowerPC 还有网络协议（IP/TCP/UDP）中仍然使用。

那么回到这道题本身上，怎么解决字节的互换问题？容易想到的方法就是把这两个字节的内容先挖出来，然后分别移位过后再填回去。由于本题给的符号限制很宽松，所以可以尽情发挥。由于1 Byte = 8 bit，所以我们先把m和n转化成实际的位数。然后让0xff（8位全1）分别左移这两个位数，得到两个对应字节处的“反掩码”。然后下一步就是把原数据x对应字节处的数据清零，将两个字节互换位置后再送进去。可得以下答案

1
2
3
4
5
6
7
8
9
10
int byteSwap(int x, int n, int m) {
   int m_bitnum = m << 3; // 获取实际的左/右移位数
   int n_bitnum = n << 3;
   int mask_m = 0xff << m_bitnum; 
   int mask_n = 0xff << n_bitnum; // 形成反掩码，或说实际上是字节选择码
   int x_masked = x & (~(mask_m | mask_n)); // 清零要交换的两个字节
   int d_m_swap = (x & mask_m) >> m_bitnum << n_bitnum; //选出一个字节的数据，移动到另一个字节处
   int d_n_swap = (x & mask_n) >> n_bitnum << m_bitnum;
   return x_masked | d_m_swap | d_n_swap;
}

这里可以总结一下几个技巧。

  • x & 1 = x x & 0 = 0
  • x | 1 = 1 x | 0 = x
  • x * 2^k = x << k x / 2^k = x >> k
  • x & x = x | x = x
  • x & ~x = 0 x | ~x = 1
  • x ^ 0 = x x ^ 1 = ~x
  • if x==y, !(x ^ y) == 1; else !(x ^ y) == 0

掌握了以上所说的基本思想，结合这里总结的技巧，就能解决这个问题了。

removeRightmostOne

1
2
3
4
5
6
7
8
9
10
/* 
 * removeRightmostOne(x) - remove the rightmost 1 from x
 *   Example: removeRightOne(0b0110) = 0b0100, removeRightOne(0b0101) = 0b0100, removeRightOne(0) = 0
 *   Legal ops: & ~ +
 *   Max ops: 10
 *   Rating: 2
 */
int removeRightmostOne(int x) {
   return 2;
}

这个题的要求是让你移除最右侧的1，也就是从最低位开始往左数，碰到的第一个1 。这个题和原/补码转换的一些性质有关。如果你熟悉有符号数原/补码之间的转换，那么相信你能很快想到怎么解决这个题；但是当时的我并没有想到这一层，于是就做得很痛苦。

所以从哪儿入手呢？我们首先回顾一下原/反/补/移码的相关知识。

  • 原码：分一位符号位和数值位，符号位0正1负；
  • 反码：正数时和原码形式一样，负数的时候数值位取反；
  • 补码：正数的时候形式和原码一致，负数的时候数值位按位取反后在最低位加1；如果从位权的角度出发，应该说n位补码表示符号数的最高位（符号位）的位权是-2^n；
  • 移码：标准移码和补码相比，数值位的表示规则完全一致，但是符号位变成了1正0负；

而在负数的原码与补码的转换中，对于数值位，有一个简便的转换法，称为扫描法。规则如下：从数值位最低位向左扫描，遇到第一个1时停止。在原码和补码的互换时，扫描到的第一个1和它右边的0都不变，其余位取反，就可以得到转化后的数值位。以一个8位二进制数（最高位符号位）的转换为例：

[11010100]原=[10101100]补[11010100]_原=[10101100]_补

如果此时你将二者的符号位去掉，将数值位相与，结果是什么？

[1010100]&[0101100]=[0000100][1010100] \& [0101100] = [0000100]

回看这道题的要求，你想到了什么？它恰恰提取出了我们要去掉的那一位1！

所以，理论上我们只要把这个相与的结果bitSelect和原数按位异或，就可以去掉这个最右侧的1。或者，还有另一种看法，就是所求的数target和这个数的加和就是原数x。按照异或和相加的思路处理都可以。

另一方面，因为在位操作的时候实际上并不区分符号/数值位，所以我们在编程的时候可以放心大胆地将int的符号位也看作是数值位，将它当成一个无符号数来处理。

我们现在采用后一种思路。target + bitSelect = x，所以target = x - bitSelect = x + ~(bitselect) + 1。

1
2
3
4
int removeRightmostOne(int x) {
   int mask = x & (~x + 1);
   return x + ~(mask) + 1;
}

maskBelowHighest

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * maskBelowHighest(x) - set all bits below the highest bit set 
 *   Example: maskBelowHighest(0b01101011) -> 0b01111111
 *            maskBelowHighest(0b10000000) -> 0b11111111
 *            maskBelowHighest(0) -> 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int maskBelowHighest(int x)
{
   return 2;
}

这道题需要你把从最高位往下数到的第一个1以下的数字都mask成1 。这道题有个非常简单粗暴的方法，就是直接移位，然后用或运算合并，直到覆盖下面所有位。为了节省符号数，仍然采用之前用到的思想，每一次移动（处理）的位数是之前的2倍，因此有：

1
2
3
4
5
6
7
8
9
int maskBelowHighest(int x)
{
   int res = x | (x >> 1); // 2 bits processed
   res = res | (res >> 2); // 4 bits
   res = res | (res >> 4); // 8
   res = res | (res >> 8); // 16
   res = res | (res >> 16); // 32
   return res;
}

largerAbsVal

1
2
3
4
5
6
7
8
9
10
11
/*
 * largerAbsVal - return the number who has a larger Abs. if |a| == |b|, return the first.
 *   Example: largerAbsVal(-5, 3) = -5, largerAbsVal(-1, 4) = 4
 *            largerAbsVal(-3, 3) = -3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3
 */
int largerAbsVal(int a, int b) {
  return 2;
}

这个题目要求比较绝对值的大小。所以重要一点在于如何利用基本位操作和加号求绝对值。我们注意到，正数的绝对值就是它自身，而负数的绝对值需要取反后+1。因为实验明确要求不能用判断语句和分支结构，我们需要找一种表示方法来统一表示这两种操作。这个问题似乎有点困难，但是我们不妨慢慢想。

首先，我们要求出两个数的符号位，因为从直觉出发，它很有可能参与到后续的运算。这个事情也很简单，将两个数算术右移31位，就可以得到全1或者全0的符号位序列。我们称它们为sgna和sgnb；

随后我们继续看这个任务。正数无须取反，而负数需要取反。如果令上面的两个数和它们的sgna/b按位异或，就可以统一这个操作，那么只剩下+1的操作了！

因为我们目前没有任何其他中间变量，所以还是要通过这个符号位来统一表示+1和+0。怎么做呢？最朴实无华的方式就是用sgna & 1来求出末位，如果是负数那就得到1 ，如果是正数就会得到0 。和原数相加，于是我们就得到了它们的绝对值。

做完这一步，剩下的事情就很简单了，二者相减，然后将结果的符号位SF算术右移到最低位，作为一个掩码，在输出的时候作为选择器。如果a - b < 0，那么SF = 1，输出b；如果a - b >= 0，那么SF = 0，输出a。万事大吉！下面是完整的代码。

1
2
3
4
5
6
7
8
9
int largerAbsVal(int a, int b) {
   int sgna = (a >> 31);
   int sgnb = (b >> 31);
   int absa = (sgna ^ a) + (sgna & 1);
   int absb = (sgnb ^ b) + (sgnb & 1);
   int diff = (absa + (~absb) + 1); // absa - absb
   int SF = diff >> 31; // Sign Flag
   return (~SF & a) | (SF & b);
}

bitReverse

1
2
3
4
5
6
7
8
9
10
11
12
// Rating 4
/*
 * bitReverse - Reverse bits in a 32-bit word
 *   Examples: bitReverse(0x80000002) = 0x40000001
 *             bitReverse(0x89ABCDEF) = 0xF7D3D591
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int bitReverse(int x) {
    return 2;
}

这道题虽然在实验的评级里是最高的Rating 4，但是在我看来其实并不如前面这几道Rating 3那么难想。如果你对于数据结构和算法有一定的敏感度，那么相信你一定能从中“闻到”二分/分治的味道。如果你意识到了这一点，那么这一题其实并不难：我们每次将未反转的部分一分为二，第一次是前16位和后16位整体交换位置，然后递归执行，直到最后两两反转完成后，就能实现整体的反转。代码如下：

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
int bitReverse(int x) {
   int flip16;
   int high16;
   int low16;
   int rev16;
   int flip8;
   int high8;
   int low8;
   int rev8;
   int flip4;
   int high4;
   int low4;
   int rev4;
   int flip2;
   int high2;
   int low2;
   int rev2;
   int flip1;
   int high1;
   int low1;
   int rev;

   flip16 = (0xff << 8) | 0xff;
   high16 = flip16 & (x >> 16);
   low16 = (flip16 & x) << 16;
   rev16 = high16 | low16;

   flip8 = 0xff;
   flip8 = flip8 | (flip8 << 16);
   high8 = flip8 & (rev16 >> 8);
   low8 = (flip8 & rev16) << 8;
   rev8 = high8 | low8;
   
   flip4 = (0x0f << 8) | 0x0f;
   flip4 = flip4 | (flip4 << 16);
   high4 = flip4 & (rev8 >> 4);
   low4 = (flip4 & rev8) << 4;
   rev4 = high4 | low4;

   flip2 = (0x33 << 8) | 0x33;
   flip2 = (flip2 << 16) | flip2;
   high2  = flip2 & (rev4 >> 2);
   low2 = (flip2 & rev4) << 2;
   rev2 = high2 | low2;
   
   flip1 = (0x55 << 8) | 0x55;
   flip1 = (flip1 << 16) | flip1;
   high1 = flip1 & (rev2 >> 1);
   low1 = (flip1 & rev2) << 1;
   rev = high1 | low1;
   // int flip1 = (0x55 << 8) | 0x55; // 用这种写法比较费op，所以注释掉参考一下。
   // flip1 = (flip1 << 16) | flip1;
   // int high1 = ~flip1 & rev2;
   // int low1 = flip1 & rev2;
   // int rev = ((high1 >> 1) & flip1) | (low1 << 1);
   return rev;
}

注意事项

更详细的内容已经在实验文档中给出，请仔细阅读课程网站上的文档。

评分

来到实验根目录，执行

1
2
make
./btest

就可以查看结果的正确性。根据正确性会给出80分的基础分。剩下的20分的是根据符号数是否符合要求来给出的，需要通过执行以下命令来查看

1
./driver.pl

如果你的代码严格按照规定完成，且结果正确，得到的分数应该是100分。

当做出了更改后，请务必重新make后再查看评分。

调试

执行以下命令以检测代码是否合规：

1
./dlc bits.c

如果你的代码符合规则，则不会输出什么结果。如果有规则不符合的地方，则会有报错。例如：

1
2
3
4
linux$ ./dlc bits.c
dlc:bits.c:202:copyLSB: Illegal if
dlc:bits.c:230:conditional: Illegal constant (0xffffffff) (only 0x0 - 0xff allowed)
dlc:bits.c:245:isPositive: Warning: 10 operators exceeds max of 8

代码规范

在最后一题bitReverse中，需要先在函数开头声明所有局部变量，并且最好不要设初值，可参考本文档给出的形式。

实验总结

这个实验是ICS课程的入门作，但是对于本科学生来说也有足够的难度了。即使过了快一年，回过头来重新做这个实验，我也会在某些地方卡住，不知如何是好。我个人觉得这个实验的确是有点“凑巧”，像是一种“脑筋急转弯”，某种程度上来看考察的并不是实际的工程能力，也和是否掌握关于数据的机器表示的知识没有必然的联系。但是如果你能顺利地完成这个实验，那你一定对逻辑代数和数据的二进制表示有很深刻的理解。

本文档给出的参考代码并不是我去年提交的原始版本，而是今年我写文档的时候重新写出来的，里面有许多实现细节和去年的版本不一样。我在我的仓库下也给出了去年的代码文件，命名为old_bits.c，里面removeRightmostOne给出了更为简洁的一种解决方法，读者可以根据自行需要查看。