NaroZeol

Student

总体要求

The bits.c file contains a skeleton for each of the 13 programming puzzles. Your assignment is to complete each function skeleton using only straightline code for the integer puzzles (i.e., no loops or con- ditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to use the following eight operators: ! ̃ & ˆ | + « » A few of the functions further restrict this list. Also, you are not allowed to use any constants longer than 8 bits

大致就是说，我们需要完成13个函数，每个函数只能使用上述8个操作符，且不能使用大于8位的常数，更具体的，每一题目还会有一些限制。

第一题

题意解析

该题要求仅使用“~”和“&”实现异或操作，要求最多符号不超过14个。

解答

int xor(int a, int b) {
    return ~(~(a & ~b) & ~(~a & b));
}

思路

异或的真值表为

A/B 0 1
0 0 1
1 1 0

而“A & ~B”和“~A & B”的真值表为

A/B 0 1
0 0 0
1 1 0
A/B 0 1
0 0 1
1 0 0

可以看出如果我们能够将两者进行一个或运算，那么就可以得到异或的结果。但问题在于题目不允许使用“|”操作符，所以我们需要想办法将两者进行一个或运算。因此我们需要借助摩根定律。

摩根定律告诉我们，对于任意的A和B，有

~(A & B) = ~A | ~B
~(A | B) = ~A & ~B

我们可以将其变形为

A | B = ~(~A & ~B)

这样我们得到了或运算。 将“A & ~ B”和“~ A & B”代入，我们得到

A ^ B = (A & ~B) | (~A & B) = ~(~(A & ~B) & ~(~A & B))

这样我们就可以得到异或的结果了。

第二题

题意解析

该题要求返回最小的二进制补码负数，要求只使用! ~ & ^ | + « »

解答

int min() {
    return 1 << 31;
}

思路

补码系统下数值与其二进制表示的关系为最高位设为负权，其余位设为正权，即

x = a[n-1] * (-2)^(n-1) + a[n-2] * 2^(n-2) + ... + a[1] * 2 + a[0]

其中a[n-1]为最高位，a[0]为最低位，n为二进制位数。因此为了让数值最小，我们只需要将最高位设为1，其余位设为0即可。既然题目允许使用移位操作，那么我们只需要将1左移31位即可得到最小的二进制补码负数。

第三题

题意解析

该题要求判断输入x是否是二进制补码系统下的最大正数，要求只使用! ~ & ^ | +

注意总体要求中的限制，不能使用大于8位的常数

解答

int isTmax(int x) {
    return !(~((x + 1) ^ x)) & !!(x + 1);
}

思路

总体限制我们不能直接使用0X7FFFFFFF，因此我们需要想办法获取这个数或者找到最大正整数所满足的一些特殊规律。

个人在实践中没有找到通过给定操作获取最大正整数的方法，因此采用了另一种方法。

注意到题目给了我们“+”运算，假设我们的数位最多只有四位，则最大的正数为0111。将其加1后我们能得到1000。1000与0111做异或运算能够得到1111，刚好用1填满了所有数位，此时对其取反能够得到0000。可以证明只有0111和1111进行这样的操作之后能得到0000。因此只需将特殊情况-1排除后即可。

第四题

题意解析

该题要求判断一个数的所有奇数的位是否为1，要求只使用! ~ & ^ | + « »

解答

int allOddBits(int x) {
    int mask = 0xAA;
    mask = mask + (mask << 8) + (mask << 16) + (mask << 24);
    return !((x & mask) ^ mask);
}

思路

构造一个所有奇数位都为1的掩码（0xAAAAAAAA），然后和该掩码做与运算判断是否和掩码相等即可。注意总体要求我们不能使用大于8位的常数，因此我们需要先创建一个八位的奇数位都为1的掩码，然后再将其左移8位，16位，24位，最后将四个掩码相加即可。

第五题

题意解析

要求返回-x，要求只使用! ~ & ^ | + « »

解答

int negate(int x) {
    return ~x + 1;
}

思路

一个大家都明白的公式，在补码系统下

-x = ~x + 1

第六题

题意解析

判断输入的x是否满足 0x30(48) <= x <= 0x39(57)，即ascii码中数字0~9所对应的符号。 只允许使用! ~ & ^ | + « »

解答

int isAsciiDigit(int x) {
    int min_neg = ~0x2F;//-48
    int max_neg = ~0x39;//-(57 + 1)
    int sign_check = 1 << 31;

    return !!(~((x + min_neg) & sign_check ) & ((x + max_neg) & sign_check));
}

思路

该题要求完成比较操作

如果A > B，那么 A - B > 0，所以我们只要创造出相减数即可。

更具体的，我们构建出-48, 如果x - 48 >= 0，则x - 48的符号位将是表示非负数的0。我们只用检查符号位即可判断x是否大于等于48。

但对于小于等于操作，情况稍微有点不一样了。x <= 57，则有 x - 57 <= 0，问题在于小于判断和等于判断无法再一次通过检查符号位获得了，因此，我们应该改写x - 57 <= 0 为 x - 58 < 0，这样就可以判断x - 58的符号位是否为1来确认是否满足。

思考

如果阅读后面的章节我们会明白CPU中的判断是否大于小于不仅要去检查符号位，还要去检查溢出信号。这是因为如果一次运算造成了溢出，那么通过检查符号位来判断是否大于小于的方法就会得到相反的结果。但问题在于为什么本题没有发生这样的错误。这是因为我们的做法通过将两个涉及大于小于判断的计算的结果与在了一起，这导致就算发生了溢出两者的影响相互抵消了，所以总体上没有什么错误。但是要记住这个做法只不过是碰巧对了罢了。

第七题

题意解析

要求实现一个三目运算符，只可使用! ~ & ^ | + « »

解答

int conditional(int x, int y, int z) {
    int flag = ((!!x) << 31) >> 31;

    return (y & flag) | (z & ~flag);
}

思路

核心就在于如何表示选择关系。

注意到-1（即0xFFFFFFFF），每一位都为1，将其与某个数做与运算则可以表示原数，而对其取反（即0），将其与某个数做与运算则可以消除该数。

因此我们只需让flag在x为非零时为0xFFFFFFFF，而为零时为0。通过表达式(y & flag) | (z & ~flag)即可表示选择关系。

0xFFFFFFFF可以通过有符号数的右移补全符号位的规则得到。

第八题

题意解析

要求实现一个判断x是否小于等于y的函数，只可以使用! ~ & ^ | + « »

解答

int isLessOrEqual(int x, int y) {
    int neg_x = ~x + 1;//-x
    int sign = 1 << 31;//sign bit
    int res = neg_x + y;//y - x

    int neg_x_AND_sign = neg_x & sign;
    int y_AND_sign = y & sign;
    int res_AND_sign = res & sign;

    int overflow_check =(neg_x_AND_sign & y_AND_sign & ~res_AND_sign) | (~neg_x_AND_sign & ~y_AND_sign & res_AND_sign);

    return (!(res_AND_sign ^ overflow_check)) | !(x ^ sign);
}

思路

和第六题类似的思路，但这次没有神奇的关系抵消溢出的问题。（见第六题思考部分，通过加减然后检查符号位的做法会因为溢出而导致结果相反）

所以我们需要修正加减法溢出时的错误。

我们需要判断x <= y，可以改写为 0 <= y + (-x)，那么只需判断y + (-x)的符号并且修正溢出的问题即可。

那么如何判断两数相加溢出了呢。首先我们应该清楚什么情况下会发生溢出。

两数相加有三种情况：

  • 一个正数一个负数，此时无论如何都不会发生溢出。
  • 两个正数，溢出会导致结果为负数。
  • 两个负数，溢出会导致结果为正数。

因此我们可以发现判断条件为

overflow_check = (As & Bs & ~Rs) | (~As & ~Bs & Rs)

其中As为一个数的符号位，Bs为另一个数的符号位，Rs为两者相加的结果的符号位。

在获得了是否溢出的信息后，我们可以通过异或操作来使得当溢出信号为1时反转结果。

 

在处理完溢出的问题后，该题还有一个很严重的问题没有解决。 我们实现 y - x时要计算-x然后再相加。当x为一个比较正常的值的时候，这个计算运行十分ok，但是当x为0x80000000（即二进制补码数的最小值）时，没有与之对应的-x。比如说以四位补码数为例，1000为最小的值，其值为-8，但是四位补码数的最大值为7，所以说不存在8与-8对应，换到32位补码数也是一个道理。不过好在对于小于等于来说，只要x为0x80000000，结果都是1。所以我们只需要加一个特例判断即可。

因为中途可能会有很多重复的信号，我们可以选择使用变量暂存信号来减少符号的使用。

第九题

题意解析

该题要求使用逻辑运算实现逻辑非(!)，可以使用除了逻辑非以外的所有逻辑运算符。

解答

int logicalNeg(int x) {
    int neg_x = ~x + 1;
    int flag = (neg_x | x ) >> 31;
    return (flag & 1) ^ 1;
}

思路

逻辑非在x为非零值时返回0，在x为零时返回1。

在补码系统下，对于一个非零值，除了最小的数以外，都存在一个相反数与之对应。也就是说非零数与其相反数之间一定有一个最高位为1。而对于零，在补码系统下只有一个唯一的表示方法，不存在+0和-0的区别。

借助这个规则，我们可以将x与其相反数做或运算，然后检查最高位是否为1。如果为1则说明该数为非零值。而对于最小的数来说，其最高位一定是1，所以此处没必要去特殊处理该情况。

最后可以用异或一个1的方式反转输出，使结果符合我们的要求。

第十题

题意解析

该题要求计算出最小能够表示一个数的最小数位的个数。

比如对于12(01100)，结果为5，前导的0是必须的，因为在补码系统下，如果无前导0则1100不是表示为12而是-8 + 4 = -4了。

再对于-5(1011)，结果为4。

特殊的要注意的是1(01)结果为2，而-1(1)结果为1。

解答

int howManyBits(int x) {
    int signFlag = 1 << 31;
    int negMask = (x & signFlag) >> 31;//当x为负数时该数每一位都为1，非负数时全为0

    int temp = 0;
    int ans = 0;
    int half = 0;
    
    x = (~x & negMask) | (x & ~negMask);//如果x为负数则取反，非负数则不变 
    temp = x;

    half = !!(temp >> 16);
    ans = ans + (half << 4);
    temp = temp >> (half << 4);

    half = !!(temp >> 8);
    ans = ans + (half  << 3);
    temp = temp >> (half << 3);

    half = !!(temp >> 4);
    ans = ans + (half << 2);
    temp = temp >> (half << 2);

    half = !!(temp >> 2);
    ans = ans + (half  << 1);
    temp = temp >> (half << 1);

    half = !!(temp >> 1);
    ans = ans + half;
    temp = temp >> half;

    ans = ans + temp;;

    return ans + 1;
}

思路

该题较为复杂。

对于非负数，最少能表示该数的位数就是最高为1的位数再加1。

而对于负数，我们发现最少能表示该数的位数是最高位0的位数再加1。

如果我们将负数取反，那么就可以用相同的方式计算了。

计算的关键就在于找到最高的1所在的位数。我们可以采用二分查找的思想来寻找这个数值。

在我们的计算机中，int值按32位存储，我们可以通过右移16位然后再检查是否为0来确定最高的1是否在高16位。

比如对于0x7AAAAAA，右移16位检查后不为0，则可以确定最高的1在高16位。

如果检查发现在高16位，我们将数据右移16位（比如说0x7AAAAAA将得到00000111 10101010），如果检查发现在低16位则不进行右移。随后再去检查新的数据中的高8位是否存在1。重复这样的过程即可得到最高的1所在的位数。

大致流程如下：

原始数据0x7AAAAAA (00000111 10101010 10101010 10101010 )

00000111 10101010 10101010 10101010 
                 ↓                  高16位不为0，则右移16位检查高16位中的情况，更新ans为16
         00000111 10101010          
                 ↓                  高8位不为0，则右移8位检查高8位中的情况，更新ans为16 + 8
             0000 0111            
                 ↓                  高4位为0，则接下来要检查的位置为低4位，不用右移，不用更新ans
               01 11               
                 ↓                  高2位不为0，则右移2位检查高2位中的情况，更新ans为16+8+0+2
                0 1                 
                 ↓                  高1位不为0，则接下来要检查的位置为低1位，不用右移，不用更新ans
                 1                  
                                    最后剩下一位为1，则更新ans为16+8+0+2+1 = 27，即为答案

然后我们只需要将为1的最高位的位数加上1就是表示该数所需要的最小位数了。

第十一题

题意解析

总算来到浮点数相关的题目了，该题给定一个32位IEEE浮点数的位级表示，要求我们给出该数乘以2后的32为IEEE浮点数的位级表示，如果输入为NAN，则返回原数。

限制条件相比于前面大幅放开，可以使用unsigned类型以及相关的所有操作，并且还给予我们使用if和while的权限。

解答

unsigned floatScale2(unsigned uf)
{
    // 31->s, 30~23->exp, 22~0->n
    unsigned sign = (1 << 31) & uf;
    unsigned exp = (uf >> 23) & 0xFF;
    unsigned n = uf & 0x7FFFFF;

    unsigned ret = 0;

    if (exp == 0xFF)
        return uf;

    if (exp)
        exp = exp + 1;
    else
        n = n << 1;

    ret = sign + (exp << 23) + n;

    return ret;
}

思路

首先我们应该对32位IEEE浮点数的组成有一定了解 从最低位开始按零计数有：

31 30~23 22 ~ 0
符号位s 阶码exp 尾数n

根据exp的值，IEEE浮点数可以分为非规格化数，规格化数和特殊的无穷大以及NAN。 以32位为例，其阶码为8位

exp的情况 种类 浮点数f的计算公式
exp != 0 && exp != 255 规格化数 f = (-1)s * (N+1) * 2exp-bias
exp == 0 非规格化数 f = (-1)s * N * 21-bias
exp == 255 无限大或NAN f = n == 0 ? (-1)s * INF : NAN

上表中N代表尾数n从最高位开始按照2-1开始计算的二进制小数，bias在32位中为127，INF为无限大，NAN为Not A Number。

从上表中可以看出，我们需要将输入进行分类讨论。

如果输入为规格化数，则我们修改exp，使其增1，则f就会变为两倍。

如果输入为非规格化数，则我们修改n，使其为原来的两倍，则f也会变为原来的两倍。

如果输入为NAN或者INF，则返回原数，按照题目要求，NAN返回原数，而INF值乘二仍然为原数。

通过判断exp的值属于哪一类，可以很轻松地获取该选择什么做法。

s,exp,n都可以通过位运算将输入拆分得到。

第十二题

题意解析

该题输入一个float值的位级表示，要求返回将该float值强转为int后的数值。当float值超出int值（包括INF和NAN）的范围时返回0x80000000。

和上题一样，允许使用所有unsigned相关的操作以及if和while。

解答

int floatFloat2Int(unsigned uf) {
    // 31->s, 30~23->exp, 22~0->n
    int tMin = 1 << 31;
    int sign = (tMin) & uf;//为负时为0x80000000，为正时为0。
    int exp = (uf >> 23) & 0xFF;
    int n = uf & 0x7FFFFF;

    int bias = 0x7f;
    int E;
    int offset;

    if (exp == 0xFF)
        return tMin;
    else if (!exp)
        return 0;
    
    E = exp - bias;
    if (E & (tMin))//E < 0, 则直接返回0
        return 0;
    else if (!((E + ~22) & (tMin))){
        return tMin;
    }
    
    n = n | (1 << 23);
    offset = 23 + (~E + 1);

    n = n >> offset;

    if (sign)
        n = ~n + 1;

    return  n;
}

思路

延续第十一题思路中的符号。我们仍然能够通过位运算来获取s，exp，n。

由十一题中的表格能够发现所有的非规格化数都是小于0的，直接返回0即可。同时题目要求输入为NAN和INF时返回0x80000000，所以我们只要考虑当输入为规格化数的情况。

对于一个浮点数，我们可以暂时不考虑其正负性，在完成处理后再将正负号添上即可。比如1.2f ->(int)1 , -1.2f -> (int)-1。这又帮助我们简化了问题。

对于规格化数，f = (-1)s * (N+1) * 2exp-bias。

关键就在于(N+1) * 2exp-bias的结果中包含了多少整数。对于一个二进制数，乘以二的n次幂就相当于向左移了n位。因为float值向int值取整是暴力向下取整，所以我们只要关注N+1向左移了exp-bias(若为负则为右移)位后整数位的情况即可。具体的我们可以看下表。

以一个6位的包含小数的二进制系统来说 1.875表示为:

22 21 20 2-1 2-2 2-3
0 0 1 1 1 1

乘以22后：

22 21 20 2-1 2-2 2-3
1 1 1 1 0 0

得到7.5。

当仅取整数位时为

22 21 20
1 1 1

即7。

所以对于(N+1) * 2exp-bias我们也能进行这样的操作。只不过有一点要注意，在计算机存储n（不是N，N代表尾数n从最高位开始按照2-1开始计算的二进制小数）时是按照正常的数位存放的。

如下表所示

n 22 21 … 2 1 0
N 2-1 2-2 … 2-21 2-22 2-23

所以我们要表示N + 1时要更新n = n | (1 « 23)。

在取整数位时也可以通过n » 23来获取整数位的情况。我们可以发现我们需要先将n左移exp - bias然后再右移23，根据位运算的规则我们可以写成右移23 - (exp - bias)。

然后处理一下正负号就得到答案了。

第十三题

题意解析

本题输入一个int值x，要求返回2x的32浮点数的位级表示。如果值太小则返回0，如果太大则返回+INF。

允许使用所有与int，unsigned有关的符号以及if， while。

解答

unsigned floatPower2(int x) {
    // 31->s, 30~23->exp, 22~0->n
    unsigned n = 0;
    unsigned exp = 0;

    int tMin = 1 << 31;
    int offset = 0;
    int bias = 0x7f;
    
    if ((x + bias + ~0) & tMin){//检查x <= bias是否成立
        offset = 23 + x;
        if (offset & tMin)
            return 0;
        
        n = 1 << offset;
    }
    else{
        exp = bias + x;
        if (!((x + ~0x7f) & tMin)){
            exp = (0x7f << 1) + 1;
        }
    }

    return (exp << 23) + n;
}

思路

此题与之前不同，要求我们自己创造一个符合规则的浮点数。

延续第十一题的设定。符号位s，阶码exp，尾数n。

观察下表：

exp的情况 种类 浮点数f的计算公式
exp != 0 && exp != 255 规格化数 f = (-1)s * (N+1) * 2exp-bias
exp == 0 非规格化数 f = (-1)s * N * 21-bias
exp == 255 无限大或NAN f = n == 0 ? (-1)s * INF : NAN

我们发现一旦x<=bias，则最后得到的一定是一个非规格化数（可以观察书中给出的按位变化表）。

对于非规格化数，根据上表公式，最后f的值只与n有关。n所对应的二进制小数即为我们最后的答案。

正如十二题中我们提到，阶码n在计算机中存储的值是按正常数位来存储的，我们需要一定的规则才能将其转换为二进制小数。

n(位模式) 22 21 … 2 1 0
N(数值) 2-1 2-2 … 2-21 2-22 2-23

观察发现，当我们需要得到2x时，n中为1的位数就是x + 23。所以为我们能确定偏移量offset=x + 23。如果得到的offset小于0则说明想要的到的值太小了，这时直接返回0就可以了。

而当x>bias，则一定是一个规格化数。

对于规格化数，因为最后结果一定是2的幂，则N应该为0，即n的所有位都为0。

当我们希望得到2x时，有exp - bias = x。变形后有exp = x + bias。这便是我们想要的exp。注意一下当exp超过最大值时我们应该返回+INF即可。

You May Also Enjoy