book
归档: 联创 
flag
mode_edit

太棒了,学到许多👍

工具链非常好用,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);
}