我面临一个相当特殊的问题。我正在为不支持按位运算的架构开发编译器。但是,它处理有符号的 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)等)
- 跳转(goto、for 等)
我希望能够支持的按位运算是:
- 或( c = a | b )
- 和( c = a & b )
- 异或( c = a ^ b )
- 左移( c = a << b )
- 右移( c = a >> b )
- (所有整数都有符号,所以这是一个问题)
- 有符号移位( c = a >>> b )
- 一个的补码( a = ~b )
- (已经找到解决方案,见下文)
通常问题是相反的。如何使用按位 hack 实现算术优化。但是在这种情况下不是。
这种架构上的可写内存非常稀缺,因此需要按位运算。按位函数本身不应使用大量临时变量。但是,常量只读数据和指令内存是丰富的。附带说明一下,跳转和分支并不昂贵,并且所有数据都可以轻松缓存。跳转花费的周期是算术(包括加载/存储)指令的一半。换句话说,所有上述支持的功能都花费了单次跳转周期的两倍。
一些可能有帮助的想法:
我发现您可以使用以下代码进行补码(否定位):
// 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;
}
或 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;
}