是否可以使用整数算术实现按位运算符？

我面临着一个相当特殊的问题。我正在为不支持按位运算的体系结构开发编译器。然而，它处理带符号的 16 位整数算术，我想知道是否可以仅使用以下方法来实现按位运算：

• Addition (c = a + b)
• 减法 (c = a - b)
• Division (c = a / b)
• 乘法 (c = a * b)
• Modulus (c = a % b)
• Minimum (c = 最小值（a，b）)
• Maximum (c = 最大值(a, b))
• 比较 (c = (a )
• Jumps (goto、for 等)

我希望能够支持的按位运算是：

• Or (c = a |乙)
• And (c = a & b)
• Xor (c = a ^ b)
• 左移 (c = a )
• 右移 (c = a >> b)
• （所有整数都有符号，所以这是一个问题）
• 有符号移位 (c = a >>> b)
• 一个的补语 (a = ~b)
• （已经找到解决办法了，见下文）

通常情况下，问题是相反的。如何使用按位黑客实现算术优化。但在本例中并非如此。

可写内存是非常稀缺在这种架构上，因此需要按位运算。按位函数本身不应使用大量临时变量。然而，恒定的只读数据和指令存储器是丰富的。这里还需要注意的是，跳转和分支并不昂贵，并且所有数据都可以轻松缓存。跳转花费的周期是算术（包括加载/存储）指令的一半。换句话说，上述所有支持的功能的成本是单次跳转周期的两倍。

一些可能有帮助的想法：

我发现你可以做一个人的补语（取反位）使用以下代码：

// Bitwise one's complement
b = ~a;
// Arithmetic one's complement
b = -1 - a;

我还记得除以二的幂时的旧移位技巧，所以按位移位可以表示为：

// Bitwise left shift
b = a << 4;
// Arithmetic left shift
b = a * 16; // 2^4 = 16

// Signed right shift
b = a >>> 4;
// Arithmetic right shift
b = a / 16;

对于其余的按位运算我有点一无所知。我希望该架构的架构师能够提供位操作。

我还想知道是否有一种快速/简单的方法可以在不使用内存数据表的情况下计算二的幂（用于移位操作）。一个简单的解决方案是跳入乘法领域：

b = 1;
switch (a)
{
  case 15: b = b * 2;
  case 14: b = b * 2;
  // ... exploting fallthrough (instruction memory is magnitudes larger)
  case 2: b = b * 2;
  case 1: b = b * 2;
}

或设置和跳跃方法：

switch (a)
{
  case 15: b = 32768; break;
  case 14: b = 16384; break;
  // ... exploiting the fact that a jump is faster than one additional mul
  //     at the cost of doubling the instruction memory footprint.
  case 2: b = 4; break;
  case 1: b = 2; break;
}

第一个移位解决方案（shift 是移位距离，不能为负数，a 是要移位的操作数，也包含完成后的结果）。所有三个班次操作均使用功率表。

// table used for shift operations
powtab = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, -32768 };

// logical shift left
if (shift > 15) {
     a = 0; // if shifting more than 15 bits to the left, value is always zero
} else {
     a *= powtab[shift];
}

// logical shift right (unsigned)
if (shift > 15) {
    a = 0; // more than 15, becomes zero
} else if (shift > 0) {
    if (a < 0) {
        // deal with the sign bit (15)
        a += -32768;
        a /= powtab[shift];
        a += powtab[15 - shift];
    } else {
        a /= powtab[shift];
    }
}

// arithmetic shift right (signed)
if (shift >= 15) {
    if (a < 0) {
        a = -1;
    } else {
        a = 0;
    }
} else if (shift > 0) {
    if (a < 0) {
        // deal with the sign bit
        a += -32768;
        a /= powtab[shift];
        a -= powtab[15 - shift];
    } else {
        // same as unsigned shift
        a /= powtab[shift];
    }
}

对于 AND、OR 和 XOR，我无法想出一个简单的解决方案，因此我将通过循环每个位来实现。可能有更好的技巧来做到这一点。伪代码假设 a 和 b 是输入操作数，c 是结果值，x 是循环计数器（每个循环必须恰好运行 16 次）：

// XOR (^)
c = 0;
for (x = 0; x <= 15; ++x) {
    c += c;
    if (a < 0) {
        if (b >= 0) {
            c += 1;
        }
    } else if (b < 0) {
        c += 1;
    }
    a += a;
    b += b;
}

// AND (&)
c = 0;
for (x = 0; x <= 15; ++x) {
    c += c;
    if (a < 0) {
        if (b < 0) {
            c += 1;
        }
    }
    a += a;
    b += b;
}

// OR (|)
c = 0;
for (x = 0; x <= 15; ++x) {
    c += c;
    if (a < 0) {
        c += 1;
    } else if (b < 0) {
        c += 1;
    }
    a += a;
    b += b;
}

假设所有变量都是 16 位并且所有操作都表现为有符号（因此当设置位 15 时 a

编辑：我实际上测试了所有可能的操作数值（-32768 到 32767）的移位范围从 0 到 31 的正确性，并且它工作正常（假设整数除法）。对于 AND/OR/XOR 代码，在我的机器上进行详尽的测试需要太长时间，但由于这些代码非常简单，所以无论如何都不应该出现边缘情况。