一、 实验目标：

1. 了解各种数据类型在计算机中的表示方法
2. 掌握C语言数据类型的位级表示及操作

二、实验环境：

1. 计算机（Intel CPU）
2. Linux操作系统

三、实验内容与步骤

实验前准备：
实验前首先需要安装GCC编译环境，在我的Ubuntu上已经安装了编译环境，展示如下：

1. 根据bits.c中的要求补全以下的函数：
   int bitXor(int x, int y);
   int tmin(void);
   int isTmax(int x);
   nt allOddBits(int x);
   int negate(int x);
   int isAsciiDigit(int x);
   int conditional(int x, int y, int z);
   int isLessOrEqual(int x, int y);
   int logicalNeg(int x);
   int howManyBits(int x);
   unsigned float_twice(unsigned uf);
   unsigned float_i2f(int x);
   int float_f2i(unsigned uf);
2. 在Linux下测试以上函数是否正确，指令如下：

• 编译：./dlc bits.c
• 测试：make btest
  ./btest

四、实验结果

1. 根据bits.c中的要求补全以下的函数

（1）int bitXor(int x, int y);

①题目描述：
仅允许使用~和&来实现异或
例子: bitXor(4, 5) = 1
允许的操作符: ~ &
最多操作符数目: 14
②大致思路：
依离散数学知识，可以列出对于单个bit的真值表如下：

X	Y	Output
0	0	0
0	1	1
1	0	1
1	1	0

即有

$Output=(\sim X\&Y)|(X\&\sim Y)$

又因为按位或不为合法运算符，故依德摩根律，有

$Output=\sim (\sim (\sim X\&Y)\&\sim (X\&\sim Y))$

③ 编程实现：

/*
 * 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 ~(~(~x & y) & ~(x & ~y));
}

（2）int tmin(void);

①题目描述：
返回最小的二进制补码
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 4

②大致思路：
对于32位整数，最小值即为0X 8000 0000，即将1左移31位。

③编程实现：

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

（3）int isTmax(int x);

① 题目描述：
如果x是最大的二进制补码，返回1；否则，返回0
允许的操作符: ! ~ & ^ | +
最多操作符数目: 10
分值: 2
②大致思路：
可以知道，最大值为0x7fff ffff，加一后将变为0x8000 0000，且此数加上本身后将变为0。本身加本身为0的数只有0和0x8000 0000，因此，只需将0xffffffff排除即可：

③编程实现：

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 2
 */
int isTmax(int x) {
    return (!(x + 1 + x + 1)) & (!!(x + 1));
}

（4）int allOddBits(int x);

①题目描述：
如果所有奇数位都为1则返回1;否则返回0
例子： allOddBits(0xFFFFFFFD) = 0
allOddBits(0xAAAAAAAA) = 1
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 12

②大致思路：
在二进制下，有且仅有所有位为奇数的数与0x5555 5555进行与运算后由0xffff ffff，变为0x0000 0000。因此可以通过对其与0x5555 5555进行与运算并取反再进行取逻辑反获得结果。又因为题干中不允许使用大于256的整数，故需要通过一些操作获得0x5555 5555。
可以通过将0x0505分别进行左移4、8、16、24得到4个数，并将四个数求和获得0x5555 5555。

③编程实现：

/*
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
    unsigned int a = 85;
    unsigned int b = a + (a << 8) + (a << 16) + (a << 24);
    return !~(b | x);
}

（5）int negate(int x);

①题目描述：
返回x的相反数
例子: negate(1) = -1.
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 5

②大致思路：
即取反并加一返回即可。

③编程实现：

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

（6）int isAsciiDigit(int x);

①题目描述：
如果x是ascii码中的0~9，返回1;否则返回0
例子: isAsciiDigit(0x35) = 1.
isAsciiDigit(0x3a) = 0.
isAsciiDigit(0x05) = 0.
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 15

②大致思路：
即对于每个输入的x，需要满足x>=‘0’且x<=‘9’，因此可以将x与临界值进行作差。并通过右移31位判断对符号位进行判断是0还是1即可。

③编程实现：

/*
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
    return (!((x + ~48 + 1) >> 31)) & !!((x + ~58 + 1) >> 31);
}

（7）int conditional(int x, int y, int z);

①题目描述：
实现x？y:z
例子: conditional(2,4,5) = 4
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 16

②大致思路：
首先，不难想到，对于x的判断可以通过t=!x进行判断实现，当x为0时返回1；当x不为0时返回0。因此，可以将表达式大致转成( _ &y)|( _ &z)的格式进行配凑。
对于前面的空格，当x不为0，即t=0时，需要 t转换为0xffff ffff（-1）。可以通过对1按位取反再加一1获得。
对于后面的空格，当x为0，即t=1时，也需要 t转换为0xffff ffff（-1）。此时直接对t进行取反并加一即可。

③编程实现：

/*
 * conditional - same as x ? y : z
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
    return ((!x + ~1 + 1) & y) | ((~!x + 1) & z);
}

（8）int isLessOrEqual(int x, int y);

①题目描述：
如果x<=y返回1否则返回0
例子: isLessOrEqual(4,5) = 1.
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 24

②大致思路：
首先应该很容易会想到直接采用y-x并判断符号位的方法进行判断，但如果作差相减，有可能会发生int类型溢出，因此需要考虑其他方法。
a. 当x，y同号：此时，即可将问题转化为转换为p=y-x>=0，并对p的符号位（通过右移获得）进行判断，获得运行结果。

b.当x，y异号：此时只要x>=0，就可以返回0，否则返回1。

c.是否同号的判断：可以通过对符号位进行求和判断是否同号。

③编程实现：

/*
 * 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 a = x >> 31;
    int b = y >> 31;
    int c = a + b;
    int p = y + (~x + 1);
    int q = !((p >> 31) & 1);
    int r = (c & (a & 1)) | ((~c) & q);
    return r;
}

（9）int logicalNeg(int x);

①题目描述：
实现！运算符的功能
例子: logicalNeg(3) = 0, logicalNeg(0) = 1
允许的操作符: ~ & ^ | + << >>
最多操作符数目: 12

②大致思路：
可以通过取相反数进行非零判断。令y=~x+1（y=-x）并讨论x与y的符号位，有如下几种情况：
a. 当x为0时，两者符号位都为0。
b. 当x=0x8000 0000时，两者符号位都为1。
c. 当x既不为0也不为0x8000 0000时，两者符号位为01或10。
因此，可依真值表得

$ans=(\sim x)\&(\sim y)$

③编程实现：

/*
 * logicalNeg - implement the ! operator, using all of
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int logicalNeg(int x) {
    return ((~(~x + 1) & ~x) >> 31) & 1;
}

（10）int howManyBits(int x);

①题目描述：
返回将X表示为补码所需的最小有效位数。
例子: howManyBits(12) = 5
howManyBits(298) = 10
howManyBits(-5) = 4
howManyBits(0) = 1
howManyBits(-1) = 1
howManyBits(0x80000000) = 32
允许的操作符: ! ~ & ^ | + << >>
最多操作符数目: 90

②大致思路：
通过二分完成算法实现，具体设计如下：
我们举一个例子进行说明：x=0000 1000 1001 0000 0000 0000 0000 0000
a.令y=x>>16=0000 1000 1001 0000，shift16=(!!y)<<4使用(!!y)判断y是否为0，如果y为0，则返回0，说明前16位都为0，shift16=0，否则!!y=1，shift16=16，使x=x>>shift16=10001001 0000;

b.同理，令y=x>>8=0000 1000，shift8=(!!y)<<3使用(!!y) 判断y是否为0，如果y为0，则返回0，说明前8位都为0，shift8=0，否则!!y=1，shift8=8，使x=x>>shift8=00001000;

c.令y=x>>4=0000，shift4=(!!y)<<2使用(!!y) 判断y是否为0，如果y为0，则返回0，说明前4位都为0，shift4=0，否则!!y=1，shift4=4，使x=x>>shift4=00001000;

d.令y=x>>2=0000 10，shift2=(!!y)<<1使用(!!y) 判断y是否为0，如果y为0，则返回0，说明前2位都为0，shift2=0，否则!!y=1，shift2=2，使x=x>>shift2=000010;

e.令y=x>>1=0000 1，shift1=(!!y),使用(!!y) 判断y是否为0，如果y为0，则返回0，说明前1位都为0，shift1=0，否则!!y=1，shift1=1，使x=x>>shift1=00001;

f.最后对各个二分进行求和即可；

g.对于负数取反码即可，对于-1和0需要进行特殊考虑。

③编程实现：

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
    int shift1, shift2, shift4, shift8, shift16;
    int sum;
    int t = ((!x) << 31) >> 31;
    int t2 = ((!~x) << 31) >> 31;
    int op = x ^((x >> 31));
    shift16 = (!!(op >> 16)) << 4;
    op = op >> shift16;
    shift8 = (!!(op >> 8)) << 3;
    op = op >> shift8;
    shift4 = (!!(op >> 4)) << 2;
    op = op >> shift4;
    shift2 = (!!(op >> 2)) << 1;
    op = op >> shift2;
    shift1 = (!!(op >> 1));
    op = op >> shift1;
    sum = 2 + shift16 + shift8 + shift4 + shift2 + shift1;
    return (t2 & 1) | ((~t2) & ((t & 1) | ((~t) & sum)));
}

（11）unsigned float_twice(unsigned uf);

①题目描述：
以unsinged表示的浮点数二进制的二倍的二进制unsigned型
参数和结果都会被作为unsigned返回，但是会表示为二进制的单精度浮点值。
允许的操作符: 任何整数或者无符号数操作符包括： ||, &&. also if, while
最多操作符数目: 30

②大致思路：（exp表示阶码位、frac表示尾数位）
通过分析可知，共存在三种可能的情况，分别考虑如下：
a.当exp=0xff时，直接返回本身即可；

b.当exp=0时，分两种情况考虑：
当uf[22]=0时，然后将frac左移一位即可
当uf[22]=1时，将exp自增1，然后再将frac左移一位即可

c.对于其他情况，将exp自增1，然后再分两种情况：
当exp==0xff，令frac=0即可。
其余情况正常左移并返回即可

③编程实现：

/*
 * 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 int exp = 0x7f800000 & uf;
    unsigned int frac = 0x007fffff & uf;
    unsigned int s = 0x80000000 & uf;
    if (((~exp) & 0x7f800000) == 0) {
        return uf;
    } else {
        if (exp == 0) {
            if ((0x00400000 & uf) == 0) {
                frac = frac << 1;
            } else {
                exp = 0x00800000;
                frac = frac << 1;
            }
        } else {
            exp = exp + 0x00800000;
            if (((~exp) & 0x7f800000) == 0)
                frac = 0;
        }
        return (exp | frac | s);
    }
}

（12）unsigned float_i2f(int x);

①题目描述：
返回int x的unsigned浮点数的二进制形式
参数和结果都会被作为unsigned返回，但是会表示为二进制的单精度浮点值
允许的操作符: 任何整数或者无符号数操作符包括： ||, &&. also if, while
最多操作符数目: 30

②大致思路：（exp表示阶码位、frac表示尾数位）
首先，我们可以知道int型数据的表示范围为-2^31~231-1。
通过分析可知，主要有三种情况：
a.用二进制下科学计数法表示int型数时，尾数位数<=23，例如0x00008001，此时将0x8001左移24-16=8位得到frac，而exp则为127+16-1；

b.当尾数位数>23时，找到位数最末一位记作x[i]，然后对尾数的舍去分3种情况考虑，并初始化c=0：
当x[i-1]=1且x[i-2]、x[i-3]…x[0]都为0，且x[i]=1,令c=1；
当x[i-1]=1且x[i-2]、x[i-3]…x[0]不都为0，令c=1;
其余情况 令c=0；

c.特殊情况。
对于x为0或为0x8000 0000的情况，在处理前进行特判即可。

③编程实现：

/*
 * 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 abs = x;
    unsigned s = 0x80000000 & x;
    unsigned tem = 0x40000000;
    unsigned exp_sign = 0;
    unsigned exp = 0;
    unsigned frac;
    unsigned c = 0;
    if (x == 0)
        return x;
    else if (x == 0x80000000)
        return (s + (158 << 23));
    else {
        if (x < 0)
            abs = -x;
        while (1) {
            if (tem & abs)
                break;
            tem = tem >> 1;
            exp_sign = exp_sign + 1;
        }
        frac = (tem - 1) & abs;
        if (31 - 1 - exp_sign > 23) {
            int i = 30 - exp_sign - 23;
            if ((frac << (31 - (i - 1))) == 0x80000000) {
                if ((frac & (1 << i)) != 0)
                    c = 1;
            } else if ((frac & (1 << (i - 1))) != 0)
                c = 1;
            frac = frac >> i;
        } else
            frac = frac << (23 - (31 - exp_sign - 1));
        exp = 157 - exp_sign;
        return (s + (exp << 23) + frac + c);
    }
}

（13）int float_f2i(unsigned uf);

①题目描述：
返回unsigned uf的整型数的二进制形式
参数和结果都会被作为unsigned返回，但是会表示为二进制的单精度浮点值
任何超过范围的数都应该返回 0x80000000u.
允许的操作符: 任何整数或者无符号数操作符包括： ||, &&. also if, while
最多操作符数目: 30

②大致思路：（exp表示阶码位、frac表示尾数位）
为了方便进行计算，可以将uf（unsigned float）切割成符号位s，阶码exp和位数frac，分情况讨论：
a.当exp=0或exp-127<0时，返回0；
b.当exp-127>=31时候，超出表示范围，于是返回0x80000000u；
c.当exp-127<=23，根据符号位返回值num>>(23-(exp-127))

③编程实现：

/*
 * float_f2i - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int float_f2i(unsigned uf) {
    int exp = 0x7f800000 & uf;
    unsigned s = 0x80000000 & uf;
    int frac = 0x007fffff & uf;
    int frac2 = frac + 0x008fffff;
    int exp_sign = ((exp >> 23) - 127);
    if (exp == 0x7f800000)
        return 0x80000000u;
    else if (exp == 0)
        return 0;
    else if (exp_sign <= -1 && exp_sign >= -126)
        return 0;
    else if (exp == 31 && frac == 0 && s != 0)
        return 0x80000000;
    else if (exp_sign >= 31)
        return 0x80000000u;
    else if (exp_sign <= 23)
        frac2 = frac2 >> (23 - exp);
    else
        frac2 = frac2 << (exp - 23);
    if (s == 0)
        return frac2;
    else
        return -frac2;
}

2. 在Linux下测试以上函数是否正确，指令如下：
   *编译：./dlc bits.c
   *测试：make btest
   ./btest
   完成代码编写后进行编译测试：
   
   运行程序并进行测试：
   
   可以看到，代码全部正确。

五、实验总结与体会

1. 位操作比高级语言难得多
   相对于高级语言，通过使用移位取反等位操作对数值进行操作要比高级语言进行运算难的多。而且在运算过程中需要注意更多的细节。位运算也需要对底层逻辑更清楚更明确。在实验过程中，通过上网查阅资料了解不熟悉的细节，我最终顺利完成了实验。

2. 数学技巧可以起到另辟蹊径的作用：
   在本次实验中，例如第一题等，可以利用离散数学中的真值表技巧，列出真值表对函数进行求解，这也是一种好方法。

3. 不能忽略特判：
   对于后三个题中，需要特殊注意特判的情况，需要区别全0情况和全1情况进行分开讨论。对特殊值进行特判后不仅能提高代码的容错性，更能使程序逻辑更清晰。