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

Question

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

• 加法 (c = a + b)
• 减法(c = a - b)
• 除法(c = a/b)
• 乘法 (c = a * b)
• 模数 (c = a % b)
• 最小值(c = min(a, b))
• 最大值(c = max(a, b))
• 比较(c = (a < b)、c = (a == b)、c = (a <= b) 等)
• 跳转(转到、for 等)

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

• 或 (c = a | b)
• 和(c = a & b)
• 异或 (c = a ^ b)
• 左移 (c = a << b)
• 右移 (c = a >> b)
• (所有整数都有符号，因此这是一个问题)
• 有符号移位 (c = a >>> b)
• 一个人的补语 (a = ~b)
• (已经找到解决方案，见下文)

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

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

<小时/>

一些可能有帮助的想法:

我发现您可以使用以下代码进行补码(求反位):

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

我还记得除以 2 的幂时的旧移位技巧，因此按位移位可以表示为:

// 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;
}

Answer 1

移位的第一个解决方案(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<0 实际上为 true)。

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