位操作与逻辑运算-深入理解计算机系统LAB2-datalab答案与解析
我们本次讨论的主题为： 计算机系统最底层的位运算
我们的题目来自于深入理解计算机系统的LAB2作业，如果大家想要LAB2的文件的话，可以发私信给我，留下邮箱，我会给你发源文件和中文注解（其实是我不会用网盘，尴尬.jpg）
ok，话不多说，我们来看看我们的要求和解答吧
这里我就不给出原题目中的英文要求，我就直接用中文简单描述
这里面涉及到了int型，float型数据在内存中的存储方式，补码，等等操作，如果没有这些知识的同学看这些代码还是有点困难
我这里给大家整理了几个小知识点，方便大家阅读代码：
位运算符：
& 按位与 （同为1答案为1）
| 按位或 （有1答案为1）
^ 按位异或（不同为1，相同为0）
~取反 （1变0，0变1）
<<左移（整体左移，右侧补零）
>>右移（整体右移，左侧补与最高位相同的数）
逻辑运算符：
&& 逻辑与，两个数同时不为0，返回1
||逻辑或，两个数有一个为1，返回1
！逻辑非，为0返回1，其他返回0
int型整数在内存中的存储方式：
首先，int型在内存中占4个字节，共32位，每位为0或1，故共有2的32次方种组合方式，可以表达这些个数对不对
最高位为符号位，0代表为非负数，1代表负数
如果是非负数：剩下的31位表示数的大小，最多可以表达到2^32-1
如果是负数：负数以补码形式表达，比如如果我们想求-5，假设只有5位，5的二进制表达为01001，最高位符号位，那么我们将1001取反加一即为其补码，取反结果10110，加一，10111，即为其补码，这就是-5在内存中的表达形式，利用补码的表达形式可以表达的整形范围为-2^32-----2^32-1,具体为什么，如果大家有兴趣可以私信我或者上网查，这里为了节省篇幅就不展开讲解了
float型在内存中的存贮方式：
float型数据4个字节，32位
第一位为符号位，与整形数据相同
第二到第九这八位，为指数位，即代表尾数位要乘2的多少次方，可以理解为2进制的科学计数法
剩下的位为尾数位，可以理解为2进制科学计数法的底数
我们注意这几种特殊情况：
如果指数位和尾数位同时为0，根据符号位不用分别表示+0和-0
如果指数位为11111111
尾数位为0，表示正负无穷大，取决符号位
尾数位不为0，表示NAN，即不是一个数
好了，基本知识大概就是这些，我们看题目
1 bitAnd:
题目简介：不用&运算符实现按位与运算
解题思路：我们利用布尔代数的思想，根据德摩根定律进行操作，利用公式
2 getbits
题目简介：截取一个整型数的第N个字节，8位长的二进制数
解题思路：我们首先将X右移至我们要截取的字节处于最低字节，具体操作因为N为字节数，我们需要移位N*8位，对于二进制位操作来说就是N<<3，然后与0xff，即我们截取部分为1，其他部分为0的数，做到截取我们需要的字节的作用
3
题目简介：逻辑右移位,只补充0
解题思路：
首先，考虑0,只需要右移即可
再考虑正数，形如：0x0...，也只需要右移
再考虑负数 形如：0x1...,发现符号位对结果产生了干扰 ,需要补充的位为1所以 添加一个掩码（掩码只需要把符号位转为0）
观察这些掩码，很容易发现，若右移n位，则前n位应为0，所以我们构造MASK作为掩码，进行操作
掩码目的：将高位的1转化为0,。所以我们先让1移位至最高位，然后右移，得到与我们需要的数完全相反的二进制表达，然后取反即可
4
题目简介：计算一个数在计算机储存时，有多少个1
解题思路：
我们目的为统计一共有多少个1
参考了网上的大佬的做法，其主要思路为二分求和：
如何二分求和呢？
如上图：
基本思路：我们将奇数位的值和与其相邻的偶数位的值相加，和是不是为其中1的个数？
是对吧，那我们如何储存呢？我们利用位操作加的性质，先将其前N位置0（利用掩码），然后相加，进位就在前N为上，是不是就储存起来了，每次合并后相邻的两位我们视作新的一位，然后继续操作
我手写了一份操作可供参考：
5
题目简介：非运算
解题思路：我们打算通过符号位进行对这个数判断是否为0
负数直接有符号位，但是正数我们如何实现呢？
我们看下图，求补操作的实质：
如果我们将int型整数的值视为一个时钟，那么因为负数以补码形式存储，所以如下图，求补后正数变为和他对称的正数，0不变，最小的负数也不变，我们利用这个性质，使本次操作数和其补码或，使得符号位为1，然后移位操作得到结果
6
题目简介：求出32位能表示的最小数
解题思路：首先我们还是可以看上面我画的图，由于int型负数以补码形式存在，0x10000000即为最小的负数，所以左移31位即可
7
题目简介：x能否被n位二进制数完全表示
解题思路：
首先：我们利用符号位作为答案是否有效的标志位
①对于负数，我们用他的补码移位操作是否为0进行判断，如果移位之后为0，说明它在n位数的表示范围之中，反之则不行
②对于正数，我们用它本身移位操作是否为0进行判断，如果移位之后为0，说明它在n位数的表示范围之中
第二种：我在网上看到了一个大神的思路：
如果x可以用n位补码表示，那么左移多余的位的个数后再右移回来的数值一定与原值相等，这个方法利用了左移后溢出的位会被丢弃，而右移回来时的是补符号位，如果丢弃了1或者右移时补的是1都会导致值的改变，而这两种情况也正说明了x不可以只用n位补码表示。Ps: 利用溢出，太强了
8
题目简介：返回 x /(2^n)
解题思路：
1 首先考虑正数，只需要逻辑右移即可
2 再考虑负数 ，因为所有的数都是向左侧取整，所以我们如果要实现向0取整的话需要对负数进行2^N-1的修正
9
题目简介：补码
解题思路：取反加一，公式带入
10
题目简介：是否为正数
解题思路：
首先我们要排除0的干扰，非零的数的我们可以直接用符号位进行判断
如果为0，逻辑非为1，所以我们利用这个性质，与符号位等同判断即可
11
题目简介：X是否小于等于Y
解题思路：
首先我们选择利用减法来进行判断，但是符号不同时如果两个数相差过大会出现溢出状态
所以我们结合老师今天上课交给我们的操作，对符号位进行判断
我们分别取出X，Y,Y-X的符号位
然后利用这个公式来进行判断是否溢出，去除溢出的影响
解释公式：
如果符号不同，并且x为正数，则正确
如果符号相同并且相减得正，则正确
12
题目简介：log2x=n
解题思路：首先我们设立几个判断位是否有效，其作用分别为
检验：
32-16位是否有1，如果有，移位
8-16位是否有1，如果有，移位
8-4位是否有1，如果有，移位
4-2位是否有1，如果有，移位
2-1位是否有1，如果有，移位
最终进行总体运算，计算出结果，得到答案
13
题目简介：如果出现极大值，返回本身，不然，返回其相反数
解题思路：这个题目的关键就是确定这个数是否为极大值
我们利用第31-24位是否全为1和23-0位是否全为0来进行判断，如果是，返回参数，否则，返回相反数
14
题目简介：整形转化为浮点型
解题思路：由于浮点数的表示中对于负数并没有使用补码的方式，正负号完全取决于符号位，所以对于负数输入，我们需要做的第一步工作就是把它取负为正数再进行后面的操作。在这个过程我们需要记录下正负，在之后的操作中需要使用。
由于浮点数与整数表示的不同，浮点数的有效数字的位置在第0-22位的23位中，并且第一个1在规格化表示中会被省略，我们只需要第一个1以后的位数，并且我们需要知道在浮点数表示中它的指数应该为多少，所以在这个过程中我们同时需要记录第一个1出现的位置并以此决定指数。
记录左移的位数，也就是最高位的1之前的零的个数，那么32-这个数就是最后的指数。
在循环中我们将整数的有效数字提前到了最前，然后将最高位移出， 这时我们用temp保存这时的状态。供之后的舍入判断使用。
接下来，我们需要将有效位移到正确的位置上，也就是向右位移9位。
下面按照之前的记录把符号位置上正确的值。
现在已经处理好有效数字与符号部分，下面要做的就是处理指数部分。
之前说过这个数是指数的数值，注意我们需要将这个值加上偏移量127，再放入表示指数的位置中。
下面就要处理舍入的情况了，浮点数表示的舍入规则比较特殊，也是本题的难点。结合本题的情况进行介绍：
在右移之前我们保存了这时的状态，因为当右移九位后原来的低九位如果有数据就会被舍弃，我们就需要根据舍弃的这九位与未被舍弃的最后一位（也就是原数第9位，下称第9位）来判断舍入的情况。
如果舍弃的这九位的最高位为0，那么说明舍去的数值小于保留下来的最低位表示的值的二分之一，那么我们不需要舍入。
如果舍弃的这九位的最高位为1，并且后面的位有数值，那么说明舍去的数值大于第9位表示的值的二分之一，这个时候我们需要舍入，也就是把最终结果加一。
如果舍弃的这九位的最高位为1，并且后面的位都是0，这个时候正好就是第9位表示的值的二分之一。那么这个时候我们就要看第9位，如果第9位为0，那么不舍入。如果第9位为1，那么进行舍入，也就是把最终结果加一。
15：
题目简介：浮点数扩大两倍
解题思路：
我们只需要考虑图中的两种特殊情况
首先：当指数的8位都为0的时候，我们要进行的操作是对除了符号位的31位左移一位，然后加上符号位即可
然后：当指数8位都为1的时候，我们进行的操作是将小数点后的23位左移一位
剩下的指数位加一即可
0返回0
好了题目 讲解 就到这里，由于 篇幅 原因 ，可能有的题目不甚详细，有疑问的小伙伴欢迎与我私信交流，我们下篇文章再见了
