int 模块规则：

  1. 类型只能用 int ；
  2. 出现的常数 \(C\in [0,255]\) ；
  3. 运算符只能出现 ! | & ~ ^ + << >> =，除了 = 以外都算一步。

1. bitOr

只能用 ~ & 实现 Or

典中典。

1
2
3
4
5
6
int bitOr(int x, int y) {
  int notX = ~x;
  int notY = ~y;
  int nandn = notX & notY;
  return ~nandn;
}

2. anyEvenBit

判断是否有任意一个偶数位是 1

由于只能用 \(8\) 位的常数，我们考虑把所有位缩到后面八位上，再 and 一个 0x55 ，然后用两次 ! 转 bool 即可。

1
2
3
4
5
int anyEvenBit(int x) {
  int hb = (x >> 16) | x;
  int ans = ((hb >> 8) | hb) & 0x55;
  return !(!ans);
}

3. rotateLeft

实现循环左移，左移位数 \(n\in [0,31]\)

朴素思路是 (x << n) | (x >> (32 - n))

然而有两个锅，第一个锅是右移 \(32\) 是 UB ，第二个锅是由于 int 算数右移，如果 \(x\) 是负数的话就会左边全部是 \(1\) 。

笔者做法是先右移一位，然后 and 一个 ~(1 << 31) 去掉多余符号位，然后再右移 \(31-n\) ，减法用补码实现。

1
2
3
4
5
6
int rotateLeft(int x, int n) {
  int r = x << n;
  int lx = (x >> 1) & ~(1 << 31);
  int l = lx >> (32 + ~n);
  return l + r
}

但是这样是 \(9\) 步，比榜一多一步，然而我拼尽全力无法战胜，把问题扔给了某和 WHU 很像的学校的某同学，他给出了下面的做法：

1
2
3
4
5
6
7
int rotateLeft(int x, int n) {
  int t = (32 + ~n);
  int y = x >> 31;
  int r = (x ^ y) << n;
  int l = x >> 1 >> t; 
  return l ^ r;
}

异或拿了MVP！

其实仔细研究一下还是能想出来的，但是我不知道为什么没想出来。

我们考虑最后把 l, r 合并时能用的操作，这样强力的操作一共有三种：| ^ + 。虽然看上去是一样的，但是我们知道异或感性地讲能够在操作前后保存更多的信息。

基于此，我们能够注意到如果 l 不对符号位进行处理，异或 r 的时候就会让 r 取反。所以只需要在求 r 的时候先用 x 的符号位控制它取一遍反，这样后面就能抵消了。

4. greatestBitPos

求 HighBit 对应的那个 \(2\) 的某个次幂

我们考虑构造一个把没用的信息都丢掉的中间体，自然地想到这个中间体是 HighBit 后面全是 1 。然后考虑怎么搞出来，相当于用最高位把后面全部覆盖，容易想到用倍增法。

得到这个之后只需要异或“自己右移一位”就行了。

然后还有个坑，就是 -1 右移的问题，解决方案是 and 一个 ~(1 << 31) 。

1
2
3
4
5
6
7
8
9
int greatestBitPos(int x) {
  x |= (x >> 1);
  x |= (x >> 2);
  x |= (x >> 4);
  x |= (x >> 8);
  x |= (x >> 16);
  x ^= ((x >> 1) & ~(1 << 31));
  return x;
}

5. leastBitPos

求 LowBit 对应的那个 \(2\) 的某个次幂

典中典中典中典，刻进 oier's DNA 里边的 x & -x 。

道理就是取反之后低位的 \(0\) 全部变成 \(1\) ，然后补码给它加个 \(1\) ，然后进位，使得反码第一个 \(0\) 变成 \(1\) 。

1
2
3
int leastBitPos(int x) {
  return x & (~x + 1);
}

6. subOK

判断 x-y 的计算是否会出现溢出

x-y 当然使用补码实现，即 x + (~y + 1) 。

自然的想法是判断上面那个加法是否溢出，即结果的符号位和 x,y 都不一样。但是这里有个坑，INT_MIN 的补码是它自己，于是当 y=INT_MIN 的时候就会挂掉。

修正方法就是用原来的符号位判断。

1
2
3
4
int subOK(int x, int y) {
  int ans = x + 1 + ~y;
  return !(((ans ^ x) & (x ^ y)) >> 31);
}

7. satMul3

计算 3*x ，溢出需要返回 int 的极值

显然需要这样计算 3*x ：x + (x << 1) 。

然后考虑溢出问题。只判断最后一步溢出显然是不行的，乘二的时候可能已经溢出了，然后导致最后一步看上去没溢出。所以需要判断两步的溢出。

两次都不溢出可以推出：结果、x 乘二和 x 的符号位全部一样。尝试证明充分性，发现溢出的结果的符号位一定和某个操作数不一样，并且如果其他步不溢出，两个操作数的符号一定是一样的，因此存在溢出可以推出某次的结果和某个操作数符号不一样。因此可以直接使用 ovf3 = (x3 ^ x2) | (x2 ^ x) 的符号位判断溢出。

然后观察两个极值，发现 INT_MAX == ~INT_MIN 。用哪个可以通过异或 x 的符号位来控制一次取反。然后还需要设计一个控制方式来适时放出实际答案。

这个时候会发现让 ovf3 >>= 31 会更好用。全 1 不仅能用 | 抹掉答案，由于 INT_MIN 是好表示的，此时 x 符号位是 1 ，状态反了，还能补一次异或。然后还需要让答案能出来，只需要让两个极值 &ovf3 即可。

感觉是最优雅的一个题。

1
2
3
4
5
6
int satMul3(int x) {
    int x2 = x << 1;
    int ans = x2 + x;
    int ovf3 = ((ans ^ x2) | (x2 ^ x)) >> 31;
    return (ovf3 | ans) ^ (((1 << 31) ^ (x >> 31)) & ovf3);
}

8. divpwr2

除 \(2^n\) 向 \(0\) 取整

这个就很简单了，用符号位去构造一个 \(2^n-1\) （也就是最低 n 位全是 \(1\) ）加上就行了。

1
2
3
4
5
int divpwr2(int x, int n) {
    int sgn = (x >> 31);
    int dlt = (sgn << n) ^ sgn;
    return (x + dlt) >> n;
}

float 模块规则：

  1. 数据类型只能用 int, uint ，float 的传入传出使用一个和它位表示相同的 uint 实现。
  2. 禁掉函数、宏定义、数组、强制类型转换，其它没有限制。

9. float_abs

浮点数取绝对值，NAN 的绝对值是自己

简单。发现负的 NAN 一定大于（？）0xff800000，判掉就行了。

1
2
3
4
5

unsigned float_abs(unsigned uf) {
  if(uf > 0xff800000) return uf;
  return uf & 0x7fffffff;
}

10. float_i2f

实现 int 强转 float

重头戏，刷榜主战场，目前主播暂时 \(8\) 步榜一 （虽然是邪道方法）

首先搞一个框架：

  1. 判掉 INT_MIN （因为没法取绝对值）和 0 ；
  2. 判掉正负；
  3. 一直右移求位数；
  4. 左右移动调到尾数的位置；
  5. 计算舍入；
  6. 计算阶码；
  7. 加起来求答案；

注意到计算阶码可以在前面的步骤里面省掉，具体方法是设初值、算位数和算正负的时候直接用阶码的对应的运算方法加上去（比如位数每多一位加上 1 << 24 ）。

但是这样子算左右移动位数就要解方程，十分浪费。于是我们想到 switch ！直接利用 switch 枚举阶码的值，然后把左右移动的值赋给变量，这样子就能 \(0\) 步解方程了。当然这不是人干的活，我们写个程序丢给电脑干就行了。

然后我们又想到计算舍入也很麻烦，也打个表，发现舍入只需要关心后 \(8\) 位和阶码即可，我们枚举它，每个后 \(8\) 位只有两个阶码可能产生进一，我们也枚举它，枚举量大概是 \(500\) ，可以接受。因为枚举了阶码，所以直接把阶码赋值成它自己加一就行了，于是实现了 \(0\) 步计算舍入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
unsigned float_i2f(int x) 
{
    unsigned cnt = 1056964608;
    int lmov = 0;
    int rmov = 0;
    int uand = 0;
    int lst = 0;
    int lx = 0;
    switch (x)
    {
      case 0:
        return 0;
        break;
      case 0x80000000: 
        return 0xcf000000;
        break;
    }
    if(x < 0)
    {
      x = -x;
      cnt = 3204448256;
    }
    lx = x;
    while(lx >>= 1)
      cnt += 8388608;

    //枚举cnt，求lmov rmov uand
    switch(cnt)
    {
        //打表1，太长省略
    }

    lst = x & uand;
    x >>= rmov;
    x <<= lmov;

    //枚举 lst 和 cnt，给 cnt 赋值为加上偏移量之后的值；
    switch (lst)
    {
        //打表2，太长省略
    }

    return x + cnt;
}

打表程序一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(int i = 1; i <= 31; i ++)
{
    unsigned int nu = (125 + i) << 23;
    printf("case %u :\n", nu);
    if(i > 24)
    {
       printf("  rmov = %d;\n", i - 24);
       printf("  uand = %d;\n", (1 << (i - 23)) - 1);
    } 
    else printf("  lmov = %d;\n", 24 - i);
    printf("break;\n");

    nu = ((125 + i) << 23) + (1 << 31);
    printf("case %u :\n", nu);
    if(i > 24)
    {
        printf("  rmov = %d;\n", i - 24);
        printf("  uand = %d;\n", (1 << (i - 23)) - 1);
    } 
    else printf("  lmov = %d;\n", 24 - i);
    printf("break;\n");
}

打表程序二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
for(int i = 1; i < (1 << 8); i ++)
{
    int lst = i;
    printf("case %d :\n", lst);
    printf("  switch(cnt){\n");
    for(int j = 25; j <= 31; j ++)
    {
       int rmov = j - 24;
       if((i >> rmov) > 1) continue;
       if((i >> (rmov - 1)) & 1)
       {
          if((i & ((1 << (rmov - 1)) - 1)) || (i >> rmov))
          {
             unsigned nu = (125 + j) << 23;
             printf("  case %u :", nu);
             printf("    cnt = %u;\n", nu + 1);
             printf("  break;\n");
             nu += (1 << 31);
             printf("  case %u :", nu);
             printf("    cnt = %u;\n", nu + 1);
             printf("  break;\n");
          }
       }
    }
    printf("  }\n");
    printf("break;\n");
}