《CSAPP》实验一:位操作
《csapp》号称程序员圣经,虽然中文译名为《深入理解计算机系统》,但其实没那么“深”,只是覆盖面很广,一般用作计算机专业大一导论课的教科书。早就听闻书上配套的实验十分经典,这次重温新版(第三版),打算把所有的实验都做一下,也写个系列博文,好记录实验过程。实验可以在书本配套网站csapp: lab assignments下载,这篇从第一个实验 —— 位操作开始。
概述
本实验是第二章《信息的表示与处理》的配套实验,要求使用一个高度限制的c语言子集实现一些特定的逻辑,整数,浮点数的函数。延用第一章的说法,信息就是位加上下文,计算机系统中所有的信息都是由一串比特(或者说一串二进制数字)表示的,第二章就讲了c语言中整数与浮点数的编码方式,即典型地,计算机是如何用一串比特来表示整数与浮点数的:
- 无符号整数:直接二进制编码
- 有符号整数:二进制补码,最高位为负权
- 浮点数:ieee 754
同样从内存里取出4个字节 \(0x80000000\) ,把它当无符号整数看,就是 \(2147483648\);把它当有符号整数看,就是 \(-2147483648\);把它当单精度浮点数看,就是 \(-0\)。所谓上下文,就是解读这串比特的方式,横看成岭侧成峰。值得注意的是,尽管在几乎所有系统上,c语言整数与浮点数都是这么编码的,但c语言标准本身并没有这样规定,不知道有生之年能不能遇上非主流的编码方式。
如果没有完全掌握这些数字的编码方式以及c语言的位操作,是一定无法完成实验一的。实验一好就好在会让你反复回忆这些基础知识,深入细节之中,做完实验后想忘都忘不了:)
前提
尽管有c语言有标准,但undefined behavior还是太多,尤其是深入底层进行位操作的情况下,因此实验预设: 有符号整数使用32位二进制补码编码; 右移操作为算术位移,高位补符号位。实验还要求:不能使用宏;整数操作不能使用大于0xff的常量。下面就逐个函数记录实验过程了。
bitand
用~
和|
实现&
,有公式很简单,但记不住,用韦恩图辅助思考:全集表示所有位都为1,x
与y
分别表示特定位置为1的子集,想象一下~
,|
和&
的韦恩图,一下子就推出公式来了。
/* * bitand - x&y using only ~ and | * example: bitand(6, 5) = 4 * legal ops: ~ | * max ops: 8 * rating: 1 */ int bitand(int x, int y) { return ~(~x | ~y); }
getbyte
x
右移 n * 8
位,取最后一个字节即可,利用了n * 8 == n << 3
。
/* * getbyte - extract byte n from word x * bytes numbered from 0 (lsb) to 3 (msb) * examples: getbyte(0x12345678,1) = 0x56 * legal ops: ! ~ & ^ | + << >> * max ops: 6 * rating: 2 */ int getbyte(int x, int n) { return (x >> (n << 3)) & 0xff; }
logicalshift
实验预设了右移为算术位移,那么对x
右移n
位再用掩码将高位补的n
位置0即可。
/* * logicalshift - shift x to the right by n, using a logical shift * can assume that 0 <= n <= 31 * examples: logicalshift(0x87654321,4) = 0x08765432 * legal ops: ! ~ & ^ | + << >> * max ops: 20 * rating: 3 */ int logicalshift(int x, int n) { int mask = ~(((1 << 31) >> n) << 1); return (x >> n) & mask; }
bitcount
这题想了很久,正常的想法是将x
一位一位地右移,用掩码1取最低位,再求和,然而操作符数量超标:d 然后想到,用x & 1
去检查x
最后一位是否是1比较亏,可以用x & 0x00010001
,这样可以一次检查两位,最后将前后16位的结果汇总即可,然而操作符数量还是超标:d最终将x
分了8组,x & 0x11111111
,每次检查8位,用了38个操作符,终于达标。这是所有题目中用的操作符数量最多的一题了。
/* * bitcount - returns count of number of 1's in word * examples: bitcount(5) = 2, bitcount(7) = 3 * legal ops: ! ~ & ^ | + << >> * max ops: 40 * rating: 4 */ int bitcount(int x) { int mask = 0x11 + (0x11 << 8) + (0x11 << 16) + (0x11 << 24); int count = (x & mask) + ((x >> 1) & mask) + ((x >> 2) & mask) + ((x >> 3) & mask); return (count & 7) + ((count >> 4) & 7) + ((count >> 8) & 7) + ((count >> 12) & 7) + ((count >> 16) & 7) + ((count >> 20) & 7) + ((count >> 24) & 7) + ((count >> 28) & 7); }
bang
一开始想在0上面作文章,毕竟只有bang(0) = 1
,但此路不通。|
操作,二分法,逐渐把高位的1收集到低位,如x = x | (x >> 16)
,如果高位的16位有1的话,就会被收集到低位的16位上,依此二分,收集到最后一位,刚好12个操作符。
/* * bang - compute !x without using ! * examples: bang(3) = 0, bang(0) = 1 * legal ops: ~ & ^ | + << >> * max ops: 12` * rating: 4 */ int bang(int x) { x = x | (x >> 16); x = x | (x >> 8); x = x | (x >> 4); x = x | (x >> 2); x = x | (x >> 1); return ~x & 1; }
tmin
最简单的一题,要熟悉二进制补码。
/* * tmin - return minimum two's complement integer * legal ops: ! ~ & ^ | + << >> * max ops: 4 * rating: 1 */ int tmin(void) { return 1 << 31; }
fitsbits
若x
非负,考虑到n
位二进制补码能表示的最大非负数为 $0b0111...111 $ (共n-1
个1),用掩码将x
低位的n-1
位置0,检查高位的32 - (n - 1)
位是否为0即可。若x
为负,先将其转为非负数~x
,编码~x
必需的位数与编码x
的是相同的。
/* * fitsbits - return 1 if x can be represented as an * n-bit, two's complement integer. * 1 <= n <= 32 * examples: fitsbits(5,3) = 0, fitsbits(-4,3) = 1 * legal ops: ! ~ & ^ | + << >> * max ops: 15 * rating: 2 */ int fitsbits(int x, int n) { int minusone = ~0; int mask = minusone << (n + minusone); return !((x ^ (x >> 31)) & mask); }
divpwr2
x >> n
即为\(\lfloor x / 2^n \rfloor\),结果是向下取整的,但题目要求向0取整,若x
非负向下取整即是向0取整没有问题,若x
为负,需要向x
加上一个偏移值\(2^n - 1\),使得x >> n
向上取整。
/* * divpwr2 - compute x/(2^n), for 0 <= n <= 30 * round toward zero * examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2 * legal ops: ! ~ & ^ | + << >> * max ops: 15 * rating: 2 */ int divpwr2(int x, int n) { int signbit = (x >> 31) & 1; int bias = (signbit << n) + (~signbit + 1); return (x + bias) >> n; }
negate
n位二进制补码的值域是\([-2^{n-1},\ 2^{n-1} - 1]\),并不关于0对称,因此当x
为最小值时-x
是它自己。
/* * negate - return -x * example: negate(1) = -1. * legal ops: ! ~ & ^ | + << >> * max ops: 5 * rating: 2 */ int negate(int x) { return ~x + 1; }
ispositive
正数的符号位为0,0的符号位也是0,是特殊情况。
/* * ispositive - return 1 if x > 0, return 0 otherwise * example: ispositive(-1) = 0. * legal ops: ! ~ & ^ | + << >> * max ops: 8 * rating: 3 */ int ispositive(int x) { return (!!x) & (!(x >> 31)); }
islessorequal
islessorequal
等价于!isgreater
,实现isgreater
简单点:若x
y
异号,则x
必须非负y
必须为负;若x
y
同号,x - y
不会溢出,必有x - y > 0
,即x - y - 1 >= 0
,即x + ~y >= 0
,检查x + ~y
的符号位即可。
/* * islessorequal - if x <= y then return 1, else return 0 * example: islessorequal(4,5) = 1. * legal ops: ! ~ & ^ | + << >> * max ops: 24 * rating: 3 */ int islessorequal(int x, int y) { int xsign = x >> 31; int ysign = y >> 31; int hassamesign = !(xsign ^ ysign); int diffsign = (x + ~y) >> 31; int isxposyneg = (!xsign) & ysign; int isgreater = isxposyneg | (hassamesign & !diffsign); return !isgreater; }
ilog2
这道题允许90个操作符,是所有题目对操作符数量最宽松的了。ilog2
的实质是求x
最高位的1的索引,若x
高位的16位有1,则不用管低位的16位;若x
高位的8位有1,则不用管低位的24位,依次类推。实现起来还是十分巧妙的:)
/* * ilog2 - return floor(log base 2 of x), where x > 0 * example: ilog2(16) = 4 * legal ops: ! ~ & ^ | + << >> * max ops: 90 * rating: 4 */ int ilog2(int x) { int high16, high8, high4, high2, high1; high16 = (!!(x >> 16)) << 4; x = x >> high16; high8 = (!!(x >> 8)) << 3; x = x >> high8; high4 = (!!(x >> 4) << 2); x = x >> high4; high2 = (!!(x >> 2) << 1); x = x >> high2; high1 = !!(x >> 1); return high1 + high2 + high4 + high8 + high16; }
float_neg
终于到浮点数了,浮点数的题对操作符要求宽松一点,还可以用循环跟判断语句。第一题,只要对ieee754熟悉就行了。
/* * float_neg - return bit-level equivalent of expression -f for * floating point argument f. * both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representations of * single-precision floating point values. * when argument is nan, return argument. * legal ops: any integer/unsigned operations incl. ||, &&. also if, while * max ops: 10 * rating: 2 */ unsigned float_neg(unsigned uf) { int isnan = (((uf >> 23) & 0xff) == 0xff) && (uf << 9); return isnan ? uf : ((1 << 31) ^ uf); }
float_i2f
没什么技巧,十分暴力。从符号位,阶码,尾数,舍入,一个一个来。注意,float(x)
是向偶数取整的。
/* * float_i2f - return bit-level equivalent of expression (float) x * result is returned as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point values. * legal ops: any integer/unsigned operations incl. ||, &&. also if, while * max ops: 30 * rating: 4 */ unsigned float_i2f(int x) { unsigned sign = x & (1 << 31); unsigned exp = 0; unsigned frac = 0; unsigned round = 0; unsigned absx = sign ? (~x + 1) : x; unsigned tmp = absx; while ((tmp = tmp >> 1)) ++exp; frac = absx << (31 - exp) << 1; round = frac << 23 >> 23; frac = frac >> 9; if (round > 0x100) round = 1; else if (round < 0x100) round = 0; else round = frac & 1; return x ? (sign | ((exp + 0x7f) << 23) | frac) + round : 0; }
float_twice
还是很暴力,按照浮点数分类一个一个来:特殊值,直接返回;规范化的浮点数,阶码加1;非规范化的,左移一位并保持符号位不变。
/* * float_twice - return bit-level equivalent of expression 2*f for * floating point argument f. * both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representation of * single-precision floating point values. * when argument is nan, return argument * legal ops: any integer/unsigned operations incl. ||, &&. also if, while * max ops: 30 * rating: 4 */ unsigned float_twice(unsigned uf) { unsigned sign = 1 << 31; unsigned isnormalized = uf << 1 >> 24; unsigned isspecial = isnormalized == 0xff; if (isspecial || uf == 0 || uf == sign) return uf; if (isnormalized) return uf + (1 << 23); return (uf << 1) | (uf & sign); }
下一篇: 重现少女魅力 老公对夜晚不失兴趣
推荐阅读
-
数据库表的创建、管理和数据操作(实验一)
-
《CSAPP》实验一:位操作
-
SAP CDS redirect view支持写操作吗,一个实验来验证 sapSAP Cloud PlatformSAP云平台ABAPCDS view
-
【操作系统实验 / C++】在分页管理方式下采用位示图来表示主存分配情况,实现主存分配和回收(附代码)
-
数据库表的创建、管理和数据操作(实验一)
-
CSAPP: 位操作实现基本运算
-
一个32位操作系统的实现1——MBR引导
-
操作系统第一次实验报告——剖析ps命令
-
计组实验一 - 8位可控的二进制补码加减法器
-
CSAPP3e shell实验 ——在ubuntu下,亲手做一个tiny shell