（16 位）可以从 ADD 和 SUBtract 中合成按位 AND 吗？

Question

我有两个函数，add 和 sub，它们接受两个 16 位参数和 return 17 位（结果和 carry/borrow）。

我可以根据这些构建按位 "and" 函数吗？

（相当小的查找表，<300 字节，允许。运行时间与位数成比例就可以了。）

Answer 1

我发现很难猜出你的 CPU 有什么没有，因为你的问题听起来基本上什么都没有，但你的后续评论似乎认为这是理所当然的它具有所有基础知识。

所以，我假设如下：

add 和 sub，如问题中所提供。
创建 C 风格的适当机制 "function"，例如：
- 一种将寄存器保存在内存中的方法，这样它们就不会被您调用的函数占用。
- 一种按值获取参数的方法，您可以销毁它而不影响调用者。
- 一种方法 return 将结果发送给调用者。
一种在一个值小于另一个值时跳过逻辑部分的方法（类似于 X86 的 jl "jump if less"）。
- 我会写成if (a >= b) { ... }，意思是"if b is less than a, then jump past the next few instructions; afterward (otherwise), run ..."。
足以支持最多 299 字节的查找表的基础知识，如问题中指定的那样。

鉴于此，我们可以这样写（用 C 表示法）：

static int const single_bit_values[] = {
    0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100,
    0x0080, 0x0040, 0x0020, 0x0010, 0x0008, 0x0004, 0x0002, 0x0001
};

int bitwise_and(int operand1, int operand2) {
    int accumulator = 0;
    for (int i = 0; i < 16; ++i) {
        // set accumulator's bit #i if appropriate:
        if (operand1 >= single_bit_values[i] && operand2 >= single_bit_values[i]) {
            accumulator += single_bit_values[i];
        }

        // clear operands' bit #i:
        if (operand1 >= single_bit_values[i]) {
            operand1 -= single_bit_values[i];
        }
        if (operand2 >= single_bit_values[i]) {
            operand2 -= single_bit_values[i];
        }
    }
    return accumulator;
}

请注意，尽管上面使用了 && 和 for 循环，但我实际上并不假设支持其中任何一个；相反，if (... && ...) 可以很容易地扩展为嵌套的 if，并且 for 循环可以很容易地完全展开。但是上面的版本更容易让人阅读。

上面的工作方式是，它遍历从高位10000000 00000000到低位00000000 00000001的单个位值，并为每个位设置相应的值如果操作数中的相应位都已设置，则累加器中的位。唯一棘手的部分是我们如何检查两个操作数是否都已设置；我们所做的是，我们在完成相应的迭代时清除操作数中的每一位（例如，11110000 00001111 在三次迭代后变为 00010000 00001111），然后让我们编写例如operand1 >= single_bit_values[3] 表示“operand1 设置了第 3 位（第四位）”。（你明白为什么了吗？）

（16 位）可以从 ADD 和 SUBtract 中合成按位 AND 吗？

Can (16 bit) bitwise AND be synthesised from ADD and SUBtract?

bit-manipulation

bitwise-operators