太棒了，学到许多👍
工具链非常好用，make, btest, dlc 一把梭。
BitAnd
求两数的 And，德摩根定律 ，秒了
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y)
{
return ~((~x) | (~y));
}
getByte
取 x 的第 n 个字节
/*
* 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
*/
int getByte(int x, int n)
{
return ((x & (0xff << (n << 3))) >> (n << 3)) & (0xff);
}
logicalShift
逻辑右移。这个有点意思，因为题里给的是有符号数，右移是算数右移，会在高位补 0，得想办法把 0 都去掉。
大概是构造一个 mask，形如 00000111111111111... 这样的，和算数右移的结果取一下与即可。
/*
* 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
*/
int logicalShift(int x, int n)
{
return (~(((0x80 << 24) >> n) << 1)) & (x >> n);
}
bitCount
感觉是整个 lab 里第二难的题。思路是别人启发我的（雾）。考虑到对于每一位，如果该位的值是一，那么就说明这一位上有一个 1 （？？？）。那么可以合并一下信息，得到每两位里有多少个 1，就地存起来，再四位四位地统计，接着八位八位…那怎么合并信息呢？
手玩一下两位的情况可以发现，实际上，就是把高位加到低位上，也就是说，左移一下，再加就行了。注意到左移的时候会把别的奇怪的位移过来影响计算，因此需要构造一个 0101010101... 的 mask 来屏蔽掉没用的位。
类似的可以搞出来别的情况，注意到本题不允许使用长度超过 1 字节的常量，因此需要我们手动移位 xjb 构造：
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x)
{
int mask1 = 0x55 | 0x55 << 8;
int mask2 = 0x33 | 0x33 << 8;
int mask3 = 0x0f | 0x0f << 8;
int mask4 = 0xff | 0xff << 16;
int mask5 = 0xff | 0xff << 8;
mask1 = mask1 | mask1 << 16;
mask2 = mask2 | mask2 << 16;
mask3 = mask3 | mask3 << 16;
x = (x & mask1) + ((x >> 1) & mask1);
x = (x & mask2) + ((x >> 2) & mask2);
x = (x & mask3) + ((x >> 4) & mask3);
x = (x & mask4) + ((x >> 8) & mask4);
x = (x & mask5) + ((x >> 16) & mask5);
return x;
}
bang
也是有意思题。题目是让实现一个 !。
一种比较妙的思路是不断「压缩」，通过一些奇妙操作，把所有的 1 都压缩到最低位上，然后再瞎搞。
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x)
{
x |= x >> 16;
x |= x >> 8;
x |= x >> 4;
x |= x >> 2;
x |= x >> 1;
return (x & 1) ^ 1;
}
tmin
太水了，返回 INT_MIN 即可
fitBits
口区口区口区口区口区口区。最没意思又恶心的题：
/*
* 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
*/
int fitsBits(int x, int n)
{
return !(((x << (32 + ~n + 1) >> (32 + ~n + 1))) ^ x);
}
divpwr2
这个主要是在大战负数，需要给他们补上一个偏置，都整成 $2^k$ 的形式再运算。
/*
* 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
*/
int divpwr2(int x, int n)
{
int swt = ~((x >> 31) & 1) + 1;
int bias = (1 << n) + ~1 + 1;
return (x + (bias & swt)) >> n;
}
negate
送的，取反加一就没了
isPositive
判断一个有符号数是不是正的。主要是别忘了判 0（
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
int isPositive(int x)
{
return (!(x & (0x80 << 24))) & !!(x ^ 0);
}
isLessOrEqual
判断有符号整数 x 是不是小于等于有符号整数 y。
看上去好像可以直接 x - y 然后判断符号位，然而考虑 $x=2\times10^9,\,y=-2\times10^9$，发生整数溢出，当场暴毙。
但是仔细一想，这种情况只会在 x, y 符号不同的时候出现，而异号的情况下，大小关系是显然的，似乎可以分类讨论的样子。
if (x y 异号)
return x < 0;
else
return x - y < 0;
但是，我们没法用分支语句！我们先来解决一个小问题：
x ? y : z
其中 x，y，z 都是整数。
x = !!x;
x = ~x + 1;
(x & y) | (~x & z);
然后我们就可以来做这个题了：
/*
* 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 mask = 1 << 31;
int dif = x + ~y + 1;
int isl0 = !!(dif & mask) | !(dif ^ 0);
int same = ~(x ^ y) & mask;
same = !!same;
same = ~same + 1;
return !!((same & isl0) | (~same & (x & mask)));
}
ilog2
全场最难（大概）。不会做，cheat 了。
其实就是找最高位的 1 的位置。思路大概是这样的，在 32 位的整数中，如果高 16 位并非全 0，那么我们可以递归地研究这 16 位，因为最高位的 1 一定在这 16 位中。类似的，我们最终一定可以二分到我们要找的那个 1. 但是…欸，等等，位置怎么求呢？
我们需要维护一个 count，对于 $n$ 位整数的情况，如果我们接下来研究的是左边一半的区间，则需要将 count 加上 $\dfrac n 2$；如果进入了右半边的区间，则不需要动 count。
但是..怎么用位运算实现呢？？
不会，爬力。从网上学到许多。
/*
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int ilog2(int x)
{
int c = !!(x >> 16) << 4;
c += !!(x >> c >> 8) << 3;
c += !!(x >> c >> 4) << 2;
c += !!(x >> c >> 2) << 1;
c += !!(x >> c >> 1);
return c;
}
highbit
插播一个不是 lab 里的题。
这个的思路是这样的，我们可以先把最高位以下全部置为一，然后右移再加一即可。
int highbit(int x)
{
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return (x >> 1) + 1;
}
float_neg
浮点数取负。注意需要特判掉 NaN。这里可以用分支语句和多字节常量了，很快乐。
unsigned float_neg(unsigned uf)
{
// 1 8 23
if (!(((uf >> 23) & (0xff)) ^ (0xff)) && 0x7fffff & uf)
return uf;
return uf ^ 0x80000000;
}
float_i2f
把一个整型转换成对应的单精度浮点型。
这个细节多的很…首先要把 0 和 INT_MIN 处理掉，然后把负数都取一下绝对值方便判断。
考虑到尾数仅仅只有 23 个 bit 长，如果整数的最高有效位的位置高于 23，势必要进行舍入（没舍入导致 WA 的憨批）。舍入规则就是四舍六入五成双。
/*
* 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)
{
// 1 8 23
unsigned res = x & 0x80000000;
int bias = 127;
int idx = 0;
int i, exp, delta = 0;
unsigned frac = x;
if (!(x ^ 0x80000000))
return 0xcf000000;
if (x == 0)
return 0;
if (res)
frac = x = -x;
i = 0;
while (i < 32)
{
if ((1 << i) & x)
idx = i;
++i;
}
// 000001xxxxxxxxxx
// ^ ^ ^
// 31 idx 0
frac <<= 32 - idx;
exp = ((idx + bias)) & 0xff;
if ((frac & 0x1ff) > 0x100 || (frac & 0x3ff) == 0x300 )
delta = 1;
return (res | (exp << 23) | (frac >> 9)) + delta;
}
float_twice
把一个浮点数乘以二。
首先特判掉 INF, 0, NaN。
然后对于规格数，只需要把阶码加一，非规格数只需要把尾数右移一位即可。
/*
* 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)
{
int exp = (uf >> 23) & 0xff;
int frac = uf & 0x7fffff;
if ((uf & 0x7fffffff) == 0 || exp == 0xff)
return uf;
if (exp)
return (uf & (0x80000000 | ~((1 << 31) >> 8))) | ((exp + 1) << 23);
else
return (uf & ((1 << 31) >> 9)) | (frac * 2);
}