DataLab's Writeup

实验笔记
Word count: 8k   |   Reading time≈ 34 min

DataLab’s Writeup

The CS:APP Data Lab
Directions to Students

Your goal is to modify your copy of bits.c so that it passes all the
tests in btest without violating any of the coding guidelines.

  1. Files:

Makefile - Makes btest, fshow, and ishow
README - This file
bits.c - The file you will be modifying and handing in
bits.h - Header file
btest.c - The main btest program
btest.h - Used to build btest
decl.c - Used to build btest
tests.c - Used to build btest
tests-header.c- Used to build btest
dlc* - Rule checking compiler binary (data lab compiler)
driver.pl* - Driver program that uses btest and dlc to autograde bits.c
Driverhdrs.pm - Header file for optional “Beat the Prof” contest
fshow.c - Utility for examining floating-point representations
ishow.c - Utility for examining integer representations

0. Files

首先，Readme给了一个任务说明，大概就把bits.c给改一下，然后运行btest，btest会自动测试修改后的bits.c，如果你改的符合要求，就能通过测试。

接下来是一些一些文件说明，

Makefile - 用于编译 btest, fshow, ishow这几个文件
README - 那个说明文档
bits.c - 你要修改的目标文件
bits.h - bits.c包含的头文件，里面写了一些基础函数
btest.c - 测试程序的源码文件
btest.h - 测试程序包含的头文件
decl.c - 用来构建测试程序的源码之一
tests.c - 用来构建测试程序的源码之一
tests-header.c- 用来构建测试程序的源码之一
dlc* - 一个特殊设计过的编译器，是一个可执行文件，可以用于检测你所改写的程序在编译级的正确性
driver.pl* - 一个能够让btest和dlc给你写的代码自动评分的驱动
Driverhdrs.pm - 没看懂
fshow.c - 用于检查浮点型结果的程序源码
ishow.c - 用于检查整型结果的程序源码

1. Modifying bits.c and checking it for compliance with dlc

这节在教你如何使用这个lab，有几个点需要注意。

第一，bits.c有自己的编写格式要求，如果你为了达成目的不顾要求也会扣分（猜测这就是刚刚那个在编译级检测的程序做到的）

第二，调用dlc的方式。其实很简单，从Terminal进入在dlc所在的目录下，执行下面的命令就行了。

1
unix> ./dlc bits.c

但是这里有个小坑，因为这个dlc是32bit的程序，如果你的Ubuntu是64位的，而且恰好没有安装32bit的运行库，你在运行的时候就会看到明明目录里面有这个dlc，但你运行的时候就告诉你dlc不存在!

image-20230311151750074

如果你也遇到了，需要运行以下命令安装一下32bit的运行库

1
sudo apt-get install lib32z1

如果遇到问题，可以尝试先运行下面的命令更新一下apt-get，这个过程可能需要等一会。

1
2
3
sudo apt-get update

sudo apt-get dist-upgrade

第三，如下图所示，如果你的代码没有语法问题，dlc就不会有回显；但不保证是合格的，你可以通过加一个参数-e的来让dlc显示运行每个函数的操作符数量具体情况。然后写完了一个就测一遍就行。

1
unix> ./dlc -e bits.c

image-20230311153021523

2. Testing with btest

这个btest就是之前说过的用来测试自己写的代码的程序，但这个程序需要我们自己编译一遍，在btest.c所在的目录下运行以下命令就可以进行编译了。

1
unix> make btest

然后这里依然有个小坑，还是64位Ubuntu导致的，在make的时候会报错说没有bits/libc-header-start.h这个文件

image-20230311154007734

遇到这个报错的话要运行以下命令，安装这个头文件

1
sudo apt-get install gcc-multilib g++-multilib module-assistant

安装好了再次make就可以了

image-20230311154246507

会有一些warning，但无伤大雅

然后这个时候注意到gcc把使用的编译命令输出出来了，发现其中有一个-Wall参数，这个参数是用来打开warning显示的。如果我们从Makefile里面把这个参数删掉（如图），再编译就不会有warning显示了（强迫症狂喜

image-20230311155238507

image-20230311155309478

编译好了之后不知道是我的电脑有bug还是编译中有特殊的参数设置，我在GUI是看不到编译好的btest文件的，但是在Terminal可以通过ls命令看到（好奇怪，猜测也许跟64位的系统有关，不过好在后面都是在Terminal使用，看不见也问题不大。

image-20230311155532942

image-20230311155506323

接下来通过以下命令来使用btest

1
unix> ./btest [optional cmd line args]

其中[]中的部分是一些可选参数

btest支持通过传参的方式来对bits.c中的指定函数的指定参数进行进行设置，比如如果想测试名为“foo“的函数可以通过以下命令

1
./btest -f foo

而如果向向foo函数的第一个参数传入”27”可以通过

1
./btest -f foo -1 27

-h参数可以打印出btest的使用说明

由于Btest 通过在每个函数上运行数百万个测试用例，这可能需要一段时间，你可以通过-T参数可以设置最大运行时间。

-g Format output for autograding with no error messages

​ -r Give uniform weight of n for all problems

最后，每次修改bits.c程序后都要运行以下命令对btest重新进行编译

1
2
make clean
make btest

其中make clean会自动清空上一次make操作中产生的所有文件

但btest不会检测你的代码是否符合编码规则，这要用dlc来检测。

3. Helper Programs

这个lab还给了两个辅助程序用来帮你翻译浮点数和整数，整数翻译比较简单就是10进制和16进制互换以及有符号数和无符号数，浮点数稍微i有点麻烦，但你应该还记得32位浮点数的存储方式，如果忘了可以看看这篇博客

然后我把原文中的使用方式直接贴上来了，这个还算比较好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unix> make             //先编译两个文件
unix> ./ishow 0x27
Hex = 0x00000027,	Signed = 39,	Unsigned = 39

unix> ./ishow 27
Hex = 0x0000001b,	Signed = 27,	Unsigned = 27

unix> ./fshow 0x15213243
Floating point value 3.255334057e-26
Bit Representation 0x15213243, sign = 0, exponent = 0x2a, fraction = 0x213243
Normalized.  +1.2593463659 X 2^(-85)

linux> ./fshow 15213243
Floating point value 2.131829405e-38
Bit Representation 0x00e822bb, sign = 0, exponent = 0x01, fraction = 0x6822bb
Normalized.  +1.8135598898 X 2^(-126)

好！文档中的说明就此结束！终于可以开始做实验了！

首先我们打开bits.c文件，前面是一大大大段的说（fei）明（hua）

不过简单看一下

首先，不要在文件中加入<stdio.h>头文件，printf函数依然能用，只不过有warning。

第二，对于整型的任务而言：

  1. 要在每个函数中的return后面加入你所用于完成任务的表达式，在return之外，你只能进行变量的声明，比如你要计算a+b，要写成

    1
    2
    3
    int a = 1；
    int b = 1；
    return a + b；

  2. 设定的常量值属于[ 0 , 255 ] (0xff)

  3. 在函数中不能使用全局变量

  4. 你只能使用有限的几种运算符号来完成任务如 !、~、&、^、|、+、<<、>>

  5. 你不能使用if、do、while、for、switch等具有跳转功能的语句

  6. 不能使用宏

  7. 不能额外定义或调用其他函数

  8. 不能使用&&、||、-、？操作符

  9. 不能使用类型转换

  10. 不能使用其他数据类型，即不能使用数组等结构

第三，对于浮点型任务而言：

  1. 可以使用循环和判断等语句
  2. 可以使用整型和浮点型变量

但以下规则依然成立

  1. 不能使用宏
  2. 不能额外定义或调用其他函数
  3. 不能使用&&、||、-、？操作符
  4. 不能使用类型转换
  5. 不能使用其他数据类型，即不能使用数组等结构

最后，每个函数有最大的操作符数量，dlc会检测操作符数。

好的！到这里要求就结束了，正式开始做实验！

1. bitAnd

第一个函数名为bitAnd（驼峰命名法好评），源码及要求贴在下面

1
2
3
4
5
6
7
8
9
10
/* 
 * 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 2;
   }

看起来就是个按位取与，要求最大操作符数是8个，只能用～和|两种操作

也就是说要让我们通过或非两种操作来实现与操作

这显然用德摩根率就可以搞定

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

再重新编译btest检查，搞定

image-20230311171955960

2. getByte

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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;
}

这题要从x中提取指定的字节，要求最大操作符数是6个，能用! ~ & ^ | + << >>操作

这里我们比较容易想到要用0xff把不相关的字节移除，所以我们这里先将目标字节挪到最低处，但是具体要哪个字节由n来决定，因此挪动多少位也就由n决定。每挪动一个字节大小是8位，所以直接把n左移3位，相当于把n乘8，此时就代表n个字节所对应的位数，此时x再右移该位数就可以了。

1
2
3
int getByte(int x, int n) {
  return (x>>(n<<3))&0xff;
}

image-20230315012547609

3. logicalShift

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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) {
  return 2;
}

这题要我们实现一个逻辑右移，要求最大操作数是20个，能用! ~ & ^ | + << >>操作

这里回顾以下算术右移和逻辑右移，其实很简单，逻辑右移就是最高位无论是啥都补0，算术右移就是最高位是1,就补1，是0就补0，而C语言中的>>操作是算术右移，所以我们可以联想到对算术右移进行修改。而我们知道两种移位最主要的区别就在于最高位的区别，因此我们可以构造一个形如0…01….1的序列，其中0的个数就是我们右移法位数，然后与我们经算术右移得到的值相与，就能得到高位为0的逻辑右移的结果了

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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) {
  return x>>n&((~0^(1<<31))>>n<<0x1^1);
}

image-20230315012602958

4. bitCount

1
2
3
4
5
6
7
8
9
10
/*
 * 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) {
  return 2;
}

这题要我们计算输入数中1的个数，要求最大操作数是40个，能用! ~ & ^ | + << >>操作

这道题难度比较高，网上还有别的版本的讲解，可以都看看，尝试理解。

首先我们不要把输入数据当作一个数看，只需要把它当成一个由01构成的字符串。首先我们构造一个形如01010101的序列，与输入数据相与，此时得到的结果中的1表示输入序列的奇数位上有1，接下来将输入字符串右移一位，再与01010101相与，此时得到的结果中的1表示输入序列的偶数位上有1，然后将两次的结果相加，这相当于以两位为一个单元，我以8位的序列举一个例子，假设输入为10101110

10101110&01010101->00000100 然后把10101110右移一位得到11010111

11010111&01010101->01010101 然后将00000100和01010101相加得到01 01 10 01

将这个结果看作是四组，每组代表这原序列对应的两位上的1的数量，

在例子中1、2位有一个1（01），3、4位有两个1（10），5、6位有一个1（01），7、8位有一个1（01）

接下来把这个结果与00110011依次做同样的运算

01011001&00110011->00010001 但这次要右移两位

00010110&00110011->00010010 然后把结果继续相加得到0010 0011

将这个结果看作是两组，每组代表这原序列对应的四位上的1的数量，

1、2、3、4位有三个1（0011），5、6、7、8位有两个1（0010）

依次类推，可以得到8位中所有的1的数量，32位与之同理，但构造需要更多种类的掩码

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
/*
 * 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 mask01 = (0x55|0x55<<8)|((0x55|(0x55<<8))<<16);
  //构造0101 0101 0101 0101 0101 0101 0101 0101
  
  int mask0011 = (0x33|0x33<<8)|((0x33|(0x33<<8))<<16);
  //构造0011 0011 0011 0011 0011 0011 0011 0011
  
  int mask00001111 = (0x0f|0x0f<<8)|((0x0f|(0x0f<<8))<<16);
  //构造0000 1111 0000 1111 0000 1111 0000 1111
  
  int mask11111111 = 0xff|(0xff<<16);
  //构造0000 0000 1111 1111 0000 0000 1111 1111
  
  int mask116 = 0xff|(0xff<<8);
  
  int count01 = (x & mask01) + ((x >> 1) & mask01);
  
  int count0011 = (count01 & mask0011) + ((count01 >> 2) & mask0011);
  
  int count00001111 = (count0011 & mask00001111) + ((count0011 >> 4) & mask00001111);
  
  int count11111111 = (count00001111 & mask11111111) + ((count00001111 >> 8) & mask11111111); 
  
  //int count116 = (count11111111 & mask116) + (count11111111 >> 16) & mask116);
  return (count11111111 & mask116) + ((count11111111 >> 16) & mask116);
}

image-20230315012616196

5. bang

1
2
3
4
5
6
7
8
9
10
/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  return 2;
}

这道题要我们在不使用！的情况下实现！，要求最大操作数是12个，能用 ~ & ^ | + << >>操作

这道题需要我们知道两件事，第一，可以通过逐位取反加一得到相反数，第二，0的相反数还是0

知道这两件事以后我们就可以开始操作了，因为非零数取相反数后符号位会改变，而0取相反数后符号位不会改变，所以我们可以将x取反加一，与自己相或，此时若x=0,则符号位为0，否则符号位必为1。因为输入0要输出1，所以我们把或运算后的结果逐位取反，此时输入0则符号位为1，否则为0，接下来右移31位，与0x1获取符号位即可

1
2
3
4
5
6
7
8
9
10
/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  return (~(x|(~x+1))>>31)&0x1;
}

image-20230315012627462

6. tmin

1
2
3
4
5
6
7
8
9
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 2;
}

这个函数要我们找到最小的二进制整数的补码，要求最大操作数是4个，能用! ~ & ^ | + << >>操作

这个其实只要知道最小的整数是“-0”就可以很容易写出来了

很简单，把1左移31位得到0x8000就可以了

1
2
3
4
5
6
7
8
9
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1<<31;
}

image-20230315012635858

7. fitsBits

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * 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) {
  return 2;
}

这个函数要我们判断给定的数能不能用给定的位数表示，要求最大操作数是15个，能用! ~ & ^ | + << >>操作

这个函数首先要注意到n位中最高位是符号位，是不能被占用的，所以我们实际考虑的只有n-1位。这个问题实际上是让我们判断给定的数是不是在-2^(n-1)到2^(n-1)-1的这样一个区间里，所以我们只要考察两个端点的数字特征就可以（以最多8位为例）

n -2^(n-1) 2^(n-1)-1
4 -8（11111000） 7（00000111）
5 -16（11110000） 15（00001111）
6 -32（11100000） 31（00011111）

经过上表我们发现，当给定的数是负数时，第n位及更高位都为1,当给定的数是正数时，最高位都为0，因此我们可以考虑把负数转化为与整数相同的形式，即先右移n-1位，然后+1，让负数能变正，再右移一位，就可以让正数和负数都变成0了，此时再取反就得到1了。而对于比此范围大的数，左侧会有更少的1（0），在经过加一右移操作后，不会变为0，取非就会为0了。

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * 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) {
  return !(((x >> (n+(~0))) + 1)>>1);
}

但是！这里有一个超级大坑！这里如果只是这样写的话，会有一个样例总是过不了

image-20230312212037727

但是很明显，答案是错的，这个是datalab的一个bug，其实不用管也可以，但对于有强迫症的我造成伤害很大，所以我决定修了他。

要修这个bug得先知道这个bug在哪，所以我们先用gdb调试一下。

首先现在Makefile文件里面加上-g编译参数，能用gdb进行调试

重新编译btest后，在命令行输入

1
gdb btest

然后给main函数下个断点

1
b main

然后开始调试

1
run -f fitsBits -1 0x80000000 -2 0x20

开始调试以后一路按n，直到看到

1
errors = run_tests();

这个函数名看起来就是用来测试我们写的函数的，所以我们用step命令进入函数，看看是如何运行的

进去以后会看到一个很多轮的循环，这个循环是用来找我们要测的函数的，咱们这个函数是第七个，经过七次for循环后我们看到这样一行代码

1
terrors = test_function(&test_set[i]);

看函数名应该是具体测试的代码，继续用step命令进入函数

然后进去以后跑着跑着就会发现error了，是因为Time out的原因，所以我们回到btest.c里面把351行的if和里面的代码全都注释掉。

然后再重复一遍刚刚的操作，这次运行到test_function函数里面以后，前面都是一些传参不用管，运行到387行会看到另一个可疑的函数

1
2
if (args == 2) {
	    errors += test_2_arg(t->solution_funct,

继续step进入函数，发现gdb帮我们打印除了函数的参数，就是fitsBits函数

image-20230312214243114

这里f2是我们写的函数不用管，继续运行下一个

1
int rt = f2t(arg1, arg2);

这个f2t就是test函数，是我们要找的答案函数，既然答案出了问题，应该是这个函数写错了，所以我们step进入函数

image-20230312214607409

进去以后发现果然是fitsBits的答案函数，在这里我们先输入 layout split，打开源码和汇编窗口

image-20230312215313306

由于一条高级语言代码对应多条汇编语言指令，所以我们接下来使用ni指令逐条汇编指令调试，这样方便我们随时查看变量值的变化

我们先执行几条ni指令，到cmp指令后，这是一个比较指令，此时变量的赋值操作应该已经完成了，所以我们用i r指令看一下寄存器的值

image-20230312215834703

发现寄存器中存了x和TMin_n的0x80000000却没有存TMax_n的0x7fffffff，

而当我们要print两个变量的地址时发现也只有TMin_n可以print出在ecx寄存器

image-20230312220125131

因此猜测可能是原代码

1
int TMax_n = (1 << (n-1)) - 1;

产生了负溢出，尤其是我们把该函数放在64位环境下编译时输出正常，所以我们要修改一下对TMax_n的定义

所以我们最后找到test_fitBits函数在test.c文件里，这个文件里都是测试函数，找到test_fitBits的定义，加上一段重新赋值

1
2
3
4
5
6
7
8
9
10
11
int test_fitsBits(int x, int n)
{
  int TMin_n = -(1 << (n-1));
  int TMax_n = (1 << (n-1)) - 1;
  if(n == 0x20){
 	TMin_n = 0x80000000;
 	TMax_n = 0x7fffffff;
  }
  
  return x >= TMin_n && x<= TMax_n;
}

保存后再次编译btest就拿到分数了！

image-20230312220656737

8. divpwr2

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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) {
    return (x>>n);
}

这道题要我们把输入的数除以2的n次方，要求最大操作数是15个，能用! ~ & ^ | + << >>操作

最直接的想法就是直接右移，但是对于正数和负数，取整方式是不同的，正数向下取整，而负数向上取整

所以我们先去补到最近的向上取整的数就可以了

1
2
3
4
5
6
7
8
9
10
11
/* 
 * 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) {
    return (x + ((x >> 31) & ((1 << n) + (~0)))) >> n;
}

image-20230315012652082

9. negate

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

这道题要我们把输入的数转化为相反数输出，要求最大操作数是5个，能用! ~ & ^ | + << >>操作

这个其实也比较简单，首先要知道负数在计算机里是用其补码表示的。这里，如果输入的是正数，则输入原码，我们应该将其转化为对应负数的补码；而如果输入的是负数，则输入的是补码，而我们需要将其转化为原码输出。而原码求补码和补码求原码都可以用除符号位按位取反加一的方式，而符号位也是我们需要改的，因此我们直接对总体取反加一即可。

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

image-20230315012703909

10 isPositive

1
2
3
4
5
6
7
8
9
10
/* 
 * 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 2;
}

这道题要我们判断输入的数是否为整数，要求最大操作数是8个，能用! ~ & ^ | + << >>操作

这道题很容易想到通过符号位来判断，所以我们之间把x右移31位来获取符号位，但是算术右移会污染高位，所以我们与上一个构造出来的0x00000001，得到符号位。但这里还有一个小坑就是0的符号位是0，但我们要把他当负数看，所以我们最后异或上对x取非，这里可以把异或操作看作是模2加法，如果x是0，取非后是1，正好加一，如果x不是0，取非后是0，不影响结果。

1
2
3
4
5
6
7
8
9
10
/* 
 * 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>>31)&((0<<31)+1)^(!x);
}

image-20230315012714190

11. isLessOrEqual

1
2
3
4
5
6
7
8
9
10
/* 
 * 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) {
	return 2;
}

这道题要我们判断输入的x是否小于等于y，要求最大操作数是24个，能用! ~ & ^ | + << >>操作

这道题给出两种实现，第一种运算符数量超过了要求，但思想是一样的

首先判断大小，最容易想到的就是作差，但是不确定两个数的范围，若两个数符号不同直接作差可能会溢出，所以我们先来判断x和y的符号，如果x为1，y为0可以直接确定为1，反之可以确定为0，剩下我们只需要讨论两个数符号相同的情况，对于相同符号的数，我们可以通过做减法，然后考察其差的符号来判断大小。

1
2
3
4
5
6
7
8
9
10
/* 
 * 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) {
	return (!((y+~x+1)>>31)&(!((!!(x>>31))^(!!(y>>31))))) | (!!(x>>31)&((!!(x>>31))^(!!(y>>31))));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
 * 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 signx = (x>>31) & 0x1; //取x的符号
    int signy = (y>>31) & 0x1; //取y的符号
    int isSameSign = !(signx^signy); //对符号位异或取反，若相同则为1,不同则为0
    int p = !(((~x)+1+y)>>31); //~x+1为x的相反数，与y相加后相当于y-x，右移31位后取符号，此时若为负数，则为0xffffffff，若为整数，则为0x00000000，因此取逻辑非，0xffffffff变为0,0x00000000变为1
	return (isSameSign & p)|((!isSameSign) & signx); //若符号相同，且x<y，则isSameSign == 1，p == 1，则isSameSign & p为1，无论后面的结果为何，或运算后都为1。若符号相同，且x>y，则isSameSign & p为0，!isSameSign为0，则(!isSameSign) & signx为0，前后都为0，输出0。若符号不同，则(!isSameSign)为1，(!isSameSign) & signx的结果取决于x的符号，若为1（x<0,y>0)，则为1,否则为0
}

image-20230315012723391

12. ilog2

1
2
3
4
5
6
7
8
9
10
/*
 * 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) {
  return 2;
}

这道题要我们计算输入的x对2取对数，要求最大操作数是90个，能用! ~ & ^ | + << >>操作

这道题和之前计算1的个数那道题比较像。我们可以先不考虑计算机该怎么做，可以先来考虑人怎么判断一个二进制数对2求对数该怎么操作，很显然，我们直接看位置最高的1在哪位上就可以了，比如log32(00100000)，此时最高位的1在第六位上，所以就是6-1=5，因此我们就将这个问题转化为了一个寻找最高位1的问题。

对于这样一个问题，我们从高位开始考虑，首先考虑高16位，如果其中有至少一个1，则两次非运算后得到1，然后将1左移4位，即变为16，意味着最高位的1，至少在16位（最低位为第0位），然后下一轮考察高16位的高八位，以此类推，得到最终的最高位1的所在位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * 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 result = 0;
  result += !!(x>>16)<<4;
  result += !!(x>>(8+result))<<3;
  result += !!(x>>(4+result))<<2;
  result += !!(x>>(2+result))<<1;
  result += !!(x>>(1+result));
  return result;
}

image-20230315012733371

13. float_neg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
 * 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) {
 return 2;
}

这道题要我们把输入的浮点数变为负数，当输入为NaN时直接输出，要求最大操作数是10个，从这道题开始，就进入浮点数阶段了，可以使用所有操作符和定义任意大小的常量。

这个如果对浮点数的表示法很清楚的话还是很简单的。不太确定的话可以看这个。首先我们需要判断输入的数是不是NaN，根据NaN的定义我们知道，其指数部分都是1，而尾数不全为0，我们只需要根据此构建出需要的01序列，与之相与，判断结果是否和我们想要的一致即可，如果确定是NaN，则提前返回。否则，因为其和整数一样最高位为符号位，所以要变成相反数只需要把最高位变一下就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 
 * 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) {
	if((uf&0x5fffff) != 0 && (uf&0x7f800000) == 0x7f800000)
		return uf; 
 	return uf^0x80000000;
}

image-20230315012741805

14. float_i2f

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * 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) {
  return 2;
}

这道题要我们把输入的整数变为浮点数，要求最大操作数是30个

首先我们先把0和-0处理掉，如果是这两个数，直接对应输出就可以了

然后因为浮点数不用补码表示，我们先把负数都变成整数，最后再补上符号

然后根据整数和浮点数的对应关系，我们依然要找最高位的1在哪，找到以后记录下来其所在的位数，方便我们之后把第一个1左侧的0都去掉

再把x 右移8位按位与 1 得到 fraction，再来看最后 8 位是否要进位。

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
/* 
 * 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) {
	if(x == 0) return 0;
	int e = 0;
	int fraction = 0;
	int sign = (x>>31)&0x1; //获取符号
	if(x == 0x80000000) return 0x80000000 | (158 << 23); //输入为-2^31时，指数为127+31=158
	else{
		if(sign == 1)
			x = ~x+1;									//负数改成正数
		
		int tmp = x;
		while(tmp != 1)									//找最高位的1
		{
			tmp = tmp >> 1;
			e++;
		}
        
		x = x << (31 - e);								//去掉第一个1左侧的0
		fraction = (x >> 8) & 0x7fffff;					//只保留第一个1右侧的数据，但这一步可能会导致尾端的数据丢失
		x = x & 0xff;									//保留最后八位也就是可能会丢失的八位
		fraction = fraction + (x > 128 || ((x == 128) && (fraction & 0x1))); //八位最多表示255,所以超过128就表示可以进位了
		if(fraction >> 23)								//检查尾数在经过进位后有没有溢出
		{
			fraction = fraction & 0x7fffff;				//如果有就重新把溢出位去掉
			e += 1;										//但给指数+1
		}
		
	}
  return (e+127)<<23 | fraction | (sign << 31);			//最后把三部分组合
}

image-20230315012749731

15. float_twice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
 * 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) {
  return 2;
}

这道题要我们把输入的浮点数乘2，当输入为NaN时直接输出，要求最大操作数是30个

首先我们先来判断输入是什么类型的浮点数，令其与0x7f800000相与，若为0，则其为非规格化数，那么对于这种数直接右移一位就可以扩大两倍了，但要记得把符号位移完了放回去。

然后再考虑其不是NaN时，这时指数部分有值，其本身的意义就是2的次方数，所以我们直接加一就可以

最后如果都不满足，说明其是NaN，直接返回即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
 * 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) {
	if ((uf & 0x7f800000) == 0)
	{
		return ((uf & 0x7fffff) << 1) | (0x80000000 & uf);
	}
	else if ((uf & 0x7f800000) != 0x7f800000)
	{
		return uf + 0x800000;
	}  
  	return uf;
}

image-20230315012755255

image-20230315012801739

完结撒花！！！

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2021-2024 Kery
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信