异星工厂 - 无符号位移


392
1 mins.
Game

1.1 无符号位移原理

1.1.1 背景

异星工厂中的算数运算器只提供了有符号位移 (sar)，但是想要造一个高性能计算机需要实现无符号位移 (shr)。

1.1.2 sar 实现 shr 的原理

实现无符号右移有几个目标：

  • 高效：运算在 1 tick 以内（也就是说，和有符号位移速度一样快）
  • 简单：不需要太多的电路，这样才能保证计算机小巧。
  • 支持 32bit: 这样才能实现 32bit 计算机

首先，我们来看看有符号右移的原理：

有符号右移说明
x >= 0此时，sar 和 shr 的结果一致
x < 0此时，sar 和 shr 的结果不一致，可以对比下面两张图

shr

sar

1.1.3 实现负数的 无符号右移 (shr)

异星工厂中的算数运算器是 32-bit 有符号整数，我们利用加法溢出可以移除负数的最高位。

其中算数运算器的处理过程如下：

注意输出侧会有一次求和，可以利用这次求和让符号位溢出

​ 现在我们通过设置 红色信号 A 为 0x8000000 = -2147483648，就可以实现将绿色信号中 A 的符号为移除的效果。

1.1.3.1 移位修正

例子

我们用 16bit 有符号距离感，假设有一个 16-bit 数字右移 8 位 分为有符号和无符号两种讨论 A>>>8 的计算方法

将 A 设置为 0x8000000 之后，实现了下面的变换：

  • 1xxx xxxx xxxx xxxx -> 0xxx xxxx xxxx xxxx
  • 0xxx xxxx xxxx xxxx -> 1xxx xxxx xxxx xxxx

移位之后有：

  • 1xxx xxxx xxxx xxxx -> 0xxx xxxx xxxx xxxx -> 0000 0000 0xxx xxxx
  • 0xxx xxxx xxxx xxxx -> 1xxx xxxx xxxx xxxx -> 1111 1111 1xxx xxxx

这里非常接近我们需要的结果，因为我们只需要在最后两个数字的第 8 位加一个 1，就可以得到需要的结果：

  • 0000 0000 0xxx xxxx + 0000 0000 1000 0000 -> 0000 0000 1xxx xxxx
  • 1111 1111 1xxx xxxx + 0000 0000 1000 0000 -> 0000 0000 0xxx xxxx

这里我们可以设置另外两个变量 X, Y
其中 X = Y = 0100 0000 0000 0000

当 A 为负数时，X，Y 会进位，替代被溢出丢失的符号位
当 A 位正数时，X，Y 会进位，但是这时是和我们设置的常量 0x80000000 求和溢出，X + Y + 0x8000000 = 0

1.1.4 当移位 31 位时

移位 31 位时，我们发现 X 和 Y 在求和之前都已经成为 0，无法进位抵消 A 的符号位，因此需要特判 B == 31 时，输出一个 A = 1 进行修正。

至此我们已经实现了一个 1 tick 的 shr 运算单元。

1.2 无符号右移 shr 蓝图

1
0eNq1ld2OmzAQhd9lrmEV/kqCtCt1n6JVVSECk81IYCNjokYR796xaSjdDbAk6k0kE8/xmflm7AvsyxZrRUJDcgHKpWgg+XGBht5EVppv+lwjJEAaK3BAZJVZZYr0sUJNuZvLak8i01JB5wCJAn9B4nXOokaBORWobgv43U8HUGjShL0juzinoq32qPiEQafCgtrKxRJzrdhQLUvkU2rZcLAU5nwjGHlPkQNnSNzwKeKDOFXBEWQzvoBnft4UohifRgUkAe8llbek7ZKddZ1J750hfy6xG3Y2Vzt+b0YrWaZ7PGYn4gDe9Ucm5f8KGnweSDU6/VDaEynd8pfBRL/DfYVevdGZQRx4ZlXVmbK2EnjmCNnqul2h+bXXrM9srRU6PShZpSRYA5JDVjbYTZRXYbFQXG9UWLMOudgO+J8Ltj3zCMJgob/nmmqK4l+lx0Bilh9N3Rs0MisbQNbIwK1veHm5D/kKqP57qFNcolm8/mfxftj4bxN5E7jDIcvrgMzDDndX2J69QQpSfTGs1C34Byo1qokbdWG8WjOvru+FcbgNvoTbhbt1Su3bSG0Qi0f37Bqx7/NigcV5d5PchBSthDRM5OZ6y/8HKt6dMF5HIsFm/Ng98CD1lePZsM9rMnrRHThxnrY4/pZx7fw4DuJdtA277je2Ga8W

您正在使用不支持或禁用了 JavaScript 的浏览器访问我们的网站。

请考虑启用 JavaScript 以获得更好的浏览体验。

要访问真正的网站 "uocat.com"，请手动复制以下网址并在您喜欢的浏览器中打开：

https://uocat.com