还记得新年立的那个flag，好消息是，我到现在还记得我要花一个学期读完《深入理解计算机系统》这个小目标，但是坏消息很明显喽：直到现在我才想起来去看这本书，最完整的计算机基础课程。（谁让我直到暑假才有自己支配的时间呀！！）
下面来看看我做的第一个实验吧！
第一题
/* 1 √
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
第一题还是难以言喻的简单呀！大家都知道这个简单的逻辑运算：
!(p^q) = !p | !q
所以就可以得到解法：
int bitAnd(int x, int y) {
return ~((~x) | (~y));
}
第二题
/* 2 √
* 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
*/
题意是说提取一个数字的第n个字节，这个题也很简单，就是按位右移一定的位后和0xFF按位取与就可以得到，又因为是十六进制表示的数字，按位右移的位数应该是8n(n << 3)，故得到解法：
int getByte(int x, int n) {
return (x >> (n << 3)) & (0xFF);
}
第三题
/* 3 √
* 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
*/
逻辑右移和算术右移的区别只是右移的时候左端补零或者补符号位：
1001 0011 >> 3
000 10010 逻辑右移
111 10010 算术右移
而计算机（C语言）并不是直接执行逻辑右移，此题让我们实现逻辑右移，我们只需要进行右移，然后把移动位变为零即可，得到解法：
int logicalShift(int x, int n) {
int a = x & 0x80000000;
int other = x & (~0x80000000);
other >>= n;
other |= (a >> n) & (1 << (32 + ~n));
return other;
}
第四题
/* 4 √
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
题意为计算一个数字的二进制表示中有多少1 ？以下解法来自网络。。。这个题没有想出来，只能利用伟大的网络喽！
int bitCount(int x) {
int bits = 0;
int mask = 0x1 | (0x1 << 8) | (0x1 << 16) | (0x1 << 24);
bits += (x & mask);
bits += ((x >> 1) & mask);
bits += ((x >> 2) & mask);
bits += ((x >> 3) & mask);
bits += ((x >> 4) & mask);
bits += ((x >> 5) & mask);
bits += ((x >> 6) & mask);
bits += ((x >> 7) & mask);
return (bits & 0xFF) + ((bits >> 8) & 0xFF) + ((bits >> 16) & 0xFF) + ((bits >> 24) & 0xFF);
}
第五题
/* 5 √
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
绕过那道变态的题，来看第五题，题意为计算真假值的逆。刚才在网上看的那道题，不小心瞟了一眼，下面这个解法还是别人的哈！这个想法挺巧妙的，通过每次处理一半，把所有比特位集中到一个位上，因为零是没有任何1的：
int bang(int x) {
/* or the top half bytes with the bottom half bytes, so if there was a 1
* it would end up in the bottom half */
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
return (x & 1) ^ 1;
}
不过我觉得这么写太麻烦了，其实利用补码表示数字的性质一个数和它的相反数的首位一定不同
0x0(首位都是零)和0x80000000(首位都是1)除外。
所以我们看出了零的特殊之处，零和零的相反数首位都是零，所以按位或的话只有零的首位还是零，所以解法：
int bang(int x) {
return (((~x + 1) | x) >> 31) + 1;
}
第六题
/* 6 √
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
这个题可是比第一题还要水。。。0x80000000即是最小值，直接返回即可：
int tmin(void) {
//return 0x80000000;
//return 1 << 31;
return (0x80 << 24);
}
第七题
/* 7 √
* 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
*/
题意为n个比特位是否足以利用补码表示x这个数字，我们知道补码表示正数时，前面好多位都是0，负数则都是1，这也是算术右移的一个简单的性质：数值不变。所以如果可以表示，那么开始的(32-n)位都是相同的，所以得到解法：
int fitsBits(int x, int n) {
return !((x << (33 + ~n) >> (33 + ~n))^x);
}
再分享一个别人的解法：
int fitsBits(int x, int n) {
int a = x >> 31;
return !(((~x & a) + (x & ~a)) >> (n + ~0));
}//除了不太容易理解，其他还是很巧妙的吧！
第八题
/* 8 √
* 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
*/
题意还是很容易理解的，就是一个数除以一个2^n，不废话，直接看解法：
int divpwr2(int x, int n) {
int highbit = (x >> 31) & 1;
int mask = ~((~0) << (n));
int rem = x & mask;
x += (highbit & !!rem) << n;
return (x >> n);
}
第九题
/* 9 √
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
求负嘛！直接返回~x+1.
int negate(int x) {
/* Use the fact that -x = ~x + 1 in twos complement. */
return (~x) + 1;
}
第十题
/* 10 √
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
判断是否为正，通过!x判断是否为零，再看符号位判断正负，解法：
int isPositive(int x) {
return (!!x & !((x >> 31) & 1));
}
第十一题
/* 11 √
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
x <= y 也就是说isPositive(y-x)喽！y - x = y + negate(x)呗！看解法：
int isLessOrEqual(int x, int y) {
int a = y + ~x + 1;
return (!!a & !((a >> 31) & 1));
}
第十二题
/* 12 √
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
好吧！我承认这道题是这15道题里面最难的。所以，我理直气壮的说：不会！！！
int ilog2(int x) {
int mask1 = 0xFF << 24 | 0xFF << 16;
int mask2 = 0xFF << 8;
int mask3 = 0xF0;
int mask4 = 0x0C;
int output = 0;
int shift;
output = !!(x & mask1) << 4;
x >>= output;
shift = !!(x & mask2) << 3;
x >>= shift;
output += shift;
shift = !!(x & mask3) << 2;
x >>= shift;
output += shift;
shift = !!(x & mask4) << 1;
x >>= shift;
output += shift;
output += (x >> 1);
return output;
}
第十三题
/* 13 √
* 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) {
unsigned mask = 0x80000000;
unsigned NaN = 0x7FC00000;
unsigned inf = 0xFFC00000;
if (uf == NaN || uf == inf)
return uf;
return uf ^ mask;
}
剩下的两道题思路比较直接，看代码妥了：
第十四题
/*
* 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) {
/* squeeze x into 23 bits, rounding following the rounding rules */
unsigned sign, fraction, exponent = 150, temp, b = 2, top, bottom;
if (x == 0) return 0;
if (x == 0x80000000) return 3472883712u;
sign = (x & 0x80000000);
fraction = (sign) ? (-x) : (x);
temp = fraction;
while (temp & 0xFF000000) {
/* standard rounding */
temp = (fraction + (b / 2)) / (b);
b <<= 1;
exponent++;
}
while (temp <= 0x007FFFFF) {
temp <<= 1;
exponent--;
}
if (fraction & 0xFF000000) {
b = 1 << (exponent - 150);
temp = fraction / b;
bottom = fraction % b;
top = b - bottom;
/* if temp is closer to fraction/b than fraction/b + 1, or its odd,
round up */
if ((top < bottom) || ((top == bottom) & temp))
++temp;
fraction = temp;
} else {
while (fraction <= 0x007FFFFF)
fraction <<= 1;
}
return (sign) | (exponent << 23) | (fraction & 0x007FFFFF);
}
第十五题
/*
* 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 its denormalized double fraction, if its normailized, increase
* exponent, if it on the edege, decrement fraction, increment epx. */
unsigned expn = (uf >> 23) & 0xFF;
unsigned sign = uf & 0x80000000;
unsigned frac = uf & 0x007FFFFF;
if (expn == 255 || (expn == 0 && frac == 0))
return uf;
if (expn) {
expn++;
} else if (frac == 0x7FFFFF) {
frac--;
expn++;
} else {
frac <<= 1;
}
return (sign) | (expn << 23) | (frac);
}
到这里，我终于完成了第一个实验，虽然有几道题是看别人的，甚至还看不懂，但是不得不说这个实验确实加深了小生对数字表示的理解！！！
网友评论