如果使用 lc-2k 指令集完成一个乘法操作，要求复杂度是 O(log⁡n)O(\log n) 要怎么做？

问题分析

lc-2k 指令集中涉及计算的部分只有 add 和 nor 两个指令
对于一个十进制的乘法操作，我们一般的做法是 列竖式，即将两个数的每一位相乘，然后将结果相加
但是在二进制中，我们应该想到的是将被乘数（较小的）写成二进制，看每一位是否为1,如果是1,那么即乘数的 cand*2^i ，然后将所有的结果相加

Bit Mask 实现

因为要找到每一位的值是否为 1, 那么我们必然需要一个能计算 每一位逻辑的工具，在 lc-2k 中, 只能用 nor 实现
将一个数字和 0xFFFF 进行 nor 操作，就会得到全 0, 但是如果我们将 0xFFFF 的第 k 位变成 0, 再进行 nor 操作，如果返回为 0, 说明原数字k位为1, 否则为 0
所以我们需要一个常量寄存器存储全1数， 即补码 -1; 我们还需要一个 每次乘 2 的bit mask 寄存器，初始值为 -1 （这里思考的时候不要转到 机器码空间，否则用补码进行计算有点逆天，我们直接用实际效果进行反向推理，要实现 -2 -> -3 -> -5 -> -9 … 的数列，然后我们再输入到寄存器就行）
那么我们需要这些寄存器:

  • r1 存储乘数 cand, 每次自己乘 2
  • r2 存储被乘数 mplier, 不变, 作为 mask 的一个基准值
  • r3 存储结果, 每次根据 mask 结果加上判断是否加上 r1
  • r4 存储 mask, 每次自己累加 1
  • r5 存储 -1 (全1)