任务：按照要求补充13个函数，会限制你能使用的操作及数量
bitXor(x,y) 只使用 ~ 和 & 实现 ^
tmin() 返回最小补码
isTmax(x) 判断是否是补码最大值
allOddBits(x) 判断补码所有奇数位是否都是1
negate(x) 不使用负号 - 实现 -x
isAsciiDigit(x) 判断 x 是否是 ASCII 码
conditional(x, y, z) 类似于 C 语言中的 x?y:z
isLessOrEqual(x,y) x<=y
logicalNeg(x) 计算 !x (不用 ! 运算符)
howManyBits(x) 计算表达 x 所需的最少位数
floatScale2(uf) 计算 2.0*uf
floatFloat2Int(uf) 计算 (int) f
floatPower2(x) 计算 2.0的x次方
/*
* 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))); // 直接推公式，^可以使用~、&和|表示，而|又可以用~和&表示
}
推导一下公式就可以直接写出来了。
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
int one = 1;
return (one << 31); // 最小的有符号数，符号位为1，其余都是0
}
有符号数是用补码来表示的，Tmin表示最小补码数，对于1个字节大小的补码，最小补码数形式为1000 0000，C语言中int类型占4字节，即32位，所以对1左移31位来构造最小补码。
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmax(int x) {
int neg1;
neg1 = !(~x); // 如果x为-1, 则neg1为1，否则neg1为0，这里是为了排除-1的干扰
return !((~(x+1)^x)|neg1); // 给x加1，再翻转，最后和自身取异或，如果x为Tmax，则返回1，否则返回0
}
函数功能是判断x是否是有符号数的最大值，也就是补码最大值，还是拿1个字节来看，最大补码数的形式为0111 1111，代码中的neg1是为了将-1单独判断出来，因为如果只使用return后面那句(!(~(x+1)^x))的话，会导致当x=-1的时候也会返回1，判断出现错误，而改变后的返回结果可以排除-1的干扰。
/*
* allOddBits - return 1 if all odd-numbered bits in word set to 1
* where bits are numbered from 0 (least significant) to 31 (most significant)
* Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
int mask = (0xAA << 8) + 0xAA;
mask = (mask << 16) + mask; // 构造掩码
return !((x & mask) ^ mask); // &操作将x的奇数位取出，偶数位置0，之后再与掩码异或判断是否满足条件
}
构造掩码操作即可，将掩码和x进行与操作，可以让x的奇数位置不变，而偶数位置变为0。
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 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) {
int negative = 1 << 31;
int lessthan = ~(negative | 0x39); // 构造上界，如果超过，则符号位变为1
int greatthan = (~(0x30) + 1); // 构造下界，如果不足，则符号位变为1
lessthan = negative & (lessthan + x) >> 31;
greatthan = negative & (greatthan + x) >> 31;
return !(lessthan | greatthan); // 判断符号位是否为1
return 2;
}
通过上下界来判断输入的x是否在0x30~0x39的范围中，使用x分别加上界和下界，当x不在这个范围中时，通过判断符号位的变化来得出判断。
/*
* 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) {
x = !!x; // 判断x是否为0，若x=0，则x赋值为0；若x不为0，则x赋值为1
x = ~x + 1; // 得到x的补码，0的补码还是0，1的补码为-1(二进制序列全1)
return (x&y)|(~x&z); // 若x为0，则返回z；若x为1，则返回y
}
重点在于return语句，这个操作可以根据x的不同来返回不同的值。
/*
* 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 minusx = ~x + 1; // 得到-x
int result = y + minusx; // 得到y - x
int sign = (result >> 31) & 1; // 判断result的符号，如果y>=x，则sign等于0，否则等于1
int xsign = (x >> 31) & 1; // 取出x的符号
int ysign = (y >> 31) & 1; // 取出y的符号
int bitXor = xsign ^ ysign; // 判断x和y符号是否一致
return ((!bitXor)&(!sign)) | ((bitXor&xsign)); // 要么x和y符号相同并且x<=y，要么x和y符号不同并且x<0
}
判断方法：如果x和y同符号，当x<=y则返回1；或者如果x和y不同符号，那么当x<0则返回1；其余情况返回0。
这里根据y-x的结果的符号来判断x和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 | (~x + 1)) >> 31) + 1;
}
/* 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) {
// 原理：对于正数，从高位到低位，找第一个位是1的（比如是n），再加上符号位，则最少需要n+1个位；
// 对于负数，从高位到低位，找第一个位是0的（比如是n），则最少需要n位
int b16, b8, b4, b2, b1, b0; // 表示0~15、16~23、24~27、28~29、30、31的位置处是否含有1，如有，则对其赋值需要的位数
int sign = x >> 31; // 取符号位
x = (sign&~x)|(~sign&x); // 如果x为正则不变，x为负则取反，这里是为了统一正负数，我们之后只用找到含有1的位置即可
b16 = !!(x >> 16) << 4;// 先看高16位是否含有1，若有则表示至少需要16位，所以给b16赋值为16(1 << 4 = 16)
x = x >> b16; // 若有1，则原数右移16位，因为上面已经确定是否至少需要16位(针对0~15)；若没有1，则b16为0，x不用移位，继续往下面判断
b8 = !!(x >> 8) << 3; // 看剩余位的高8位是否含有1，若有则表示至少还需要8位，给b8赋值为8
x = x >> b8; // 同理...
b4 = !!(x >> 4) << 2;
x = x >> b4;
b2 = !!(x >> 2) << 1;
x = x >> b2;
b1 = !!(x >> 1);
x = x >> b1;
b0 = x;
return b16+b8+b4+b2+b1+b0+1; // 最后加上符号位
}
注释已经写的很清楚了，可以边看代码边打草稿，很容易理解。
/*
* floatScale2 - 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 floatScale2(unsigned uf) {
int exp = (uf&0x7F800000) >> 23; // 取出阶码
int sign = uf&(1 << 31); // 取符号位
if (exp == 0) return uf<<1|sign; // 若为非规格数，直接给uf乘以2后加上符号位即可
if (exp == 255) return uf; // 若为无穷大或者NaN，直接返回自身
exp = exp + 1; // 若uf乘以2（也就是阶码加1）后变成255，则返回无穷大
if (exp == 255) return (0x7F800000|sign);
return (exp << 23)|(uf&0x807FFFFF); // 返回阶码加1后的原符号数
}
需要了解计算机内浮点数的表示方法，了解浮点数中的规格数、非规格数、无穷大和未定义的区别和表示。
我们先看如何表示浮点数：
这里的uf类型为unsigned int，并不是浮点数，但是我们将uf看作为单精度类型，它有32位，最高位是符号位，之后8位保存指数信息，最后23位保存小数信息，所以在代码中我们可以看到，我们通过和0x7F800000取与操作来获得指数信息，再右移23位取出这一部分。
浮点数有几种特殊情况：
1.若exp部分全为0(exp = 0)，则是非规格化数，它是一种非常接近0的数；
2.若exp部分全为1(exp = 255)，当小数部分全为0时，表示无穷大；当小数部分不为全0时，表示未初始化数据NaN；
3.以上两种情况以外，就是规格化数。
所以我们需要判断uf是哪一种浮点数，并根据它的类型来进行相应的操作。
/*
* floatFloat2Int - 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 floatFloat2Int(unsigned uf) {
int exp = ((uf&0x7F800000) >> 23) - 127; // 计算出指数
int sign = uf >> 31; // 取符号位
int frac = ((uf&0x007FFFFF) | 0x00800000);
if (!(uf&0x7FFFFFFF)) return 0; // 若原浮点数为0，则返回0
if (exp > 31) return 0x80000000; // 若原浮点数指数大于31，返回溢出值
if (exp < 0) return 0; // 若浮点数小于0，则返回0；
if (exp > 23) frac = frac << (exp - 23); // 将小数转化为整数
else frac = frac >> (23 - exp);
if (!((frac >> 31) ^ sign)) return frac; // 判断是否溢出，若符号位没有变化，则没有溢出，返回正确的值
else if (frac >> 31) return 0x80000000; // 原数为正值，现在为负值，返回溢出值
else return ~frac + 1; // 原数为负值，现在为正值，返回相反数
}
需要了解整数和浮点数之间的转化方法，我们要做的就是将浮点数中的指数部分和小数部分取出来，然后通过这两部分来转化为整数，具体操作可以看代码，在这个过程中还要判断是否会产生溢出，以及浮点数是否为规格数等情况，如果产生溢出，我们需要返回一个特定的溢出值。
这里有一个将整数转化为浮点数的例子：
/*
* floatPower2 - Return bit-level equivalent of the expression 2.0^x
* (2.0 raised to the power x) for any 32-bit integer x.
*
* The unsigned value that is returned should have the identical bit
* representation as the single-precision floating-point number 2.0^x.
* If the result is too small to be represented as a denorm, return
* 0. If too large, return +INF.
*
* Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while
* Max ops: 30
* Rating: 4
*/
unsigned floatPower2(int x) {
int INF = 0xFF << 23; // 设定一个最大值，也就是阶码位置都为1
int exp = x + 127; // 计算阶码
if (exp <= 0) return 0; // 阶码小于等于0，则返回0
if (exp >= 255) return INF; // 阶码大于等于255，则返回INF
return exp << 23;
}
所有代码及相关实验说明材料都在这里
