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

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),et.c.)
• 跳转(goto,for,et.c.)

我希望能够支持的按位操作是:

• 或者(c = a | b)
• 并且(c = a&b)
• Xor(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;

对于其他的按位操作,我有点无能为力.我希望这个架构的架构师能够提供位操作.

我还想知道是否有一种快速/简单的方法来计算2的功率(用于移位操作)而不使用存储器数据表.一个天真的解决方案是跳进乘法领域:

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

或者Set&Jump方法:

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

用于移位的第一种解决方案(移位是移位距离,不得为负,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位时,<0实际上是真的).

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

Answer 2

一个老问题的不完整答案，这里集中于 AND、OR、XOR。一旦找到这些按位运算之一的解决方案，就可以推导出另外两个。有多种方式，一种如下面的测试程序所示（编译在gcc 4.6.3版（Ubuntu/Linaro 4.6.3-1ubuntu5）上）。

2018 年 12 月，我在解决方案中发现了一个错误。下面评论的 XOR 仅起作用，因为 中的中间结果a+b-2*AND(a,b)被提升为int，对于所有现代编译器来说，它大于 16 位。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

//#define XOR(a,b) (a + b - 2*AND(a,b)) // Error. Intermediate overflow
#define XOR(a,b) (a - AND(a,b) +  b - AND(a,b) )
#define IOR(a,b) XOR(XOR(a,b),AND(a,b)) // Credit to Jan Gray, Gray Research LLC, for IOR
static const uint16_t andlookup[256] = {
#define C4(a,b) ((a)&(b)), ((a)&(b+1)), ((a)&(b+2)), ((a)&(b+3))
#define L(a) C4(a,0), C4(a,4), C4(a,8), C4(a,12)
#define L4(a) L(a), L(a+1), L(a+2), L(a+3)
    L4(0), L4(4), L4(8), L4(12)
#undef C4
#undef L
#undef L4
};

uint16_t AND(uint16_t a, uint16_t b) {
    uint16_t r=0, i;

    for ( i = 0; i < 16; i += 4 ) {
            r = r/16 + andlookup[(a%16)*16+(b%16)]*4096;
            a /= 16;
            b /= 16;
    }
    return r;
}

int main( void ) {
    uint16_t a = 0, b = 0;

    do {
            do {
                    if ( AND(a,b) != (a&b) ) return printf( "AND error\n" );
                    if ( IOR(a,b) != (a|b) ) return printf( "IOR error\n" );
                    if ( XOR(a,b) != (a^b) ) return printf( "XOR error\n" );
            } while ( ++b != 0 );
            if ( (a & 0xff) == 0 )
                    fprintf( stderr, "." );
    } while ( ++a != 0 );
    return 0;
}

Answer 3

在这种环境下，最好设置为实际使用算术运算符来剥离整数部分。

例如

if (a & 16)  becomes if ((a % 32) > 15)
a &= 16 becomes if ((a % 32) < 15) a += 16

如果将RHS限制为2的恒定幂，则这些运算符的变换就很明显。

剥掉两个或四个位也很容易。