使用整数算术可以实现按位运算符吗？
我面临一个相当奇怪的问题。 我正在为不支持按位运算的体系结构编译器。 然而，它处理带符号的16位整数算术，我想知道是否有可能只使用下列操作来实现按位运算：
我希望能够支持的按位运算是：
通常问题是相反的; 如何使用按位黑客来实现算术优化。 但在这种情况下不是。
可写内存在此架构上非常稀缺 ，因此需要按位操作。 按位函数本身不应该使用大量的临时变量。 但是，恒定的只读数据和指令存储器非常丰富。 这里还要注意的一点是跳转和分支并不昂贵，并且所有数据都很容易被缓存。 随着算术（包括加载/存储）指令的执行，跳转花费一半的周期。 换句话说，上述所有支持的函数都会花费两次单跳的周期。
一些想法可能会有所帮助：
我发现你可以用下面的代码来完成补码 （否定比特）：
// 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;
}
第一种移位解决方案（移位是移位距离，不能是负数，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位，并且所有操作的行为都是带符号的（所以当bit 15被设置时，<0实际上是真的）。
编辑：我实际上测试了所有可能的操作数值（-32768到32767）的范围从0到31的正确性，并且它正常工作（假设整数除法）。 对于AND / OR / XOR代码，穷举测试在我的机器上花费的时间太长，但由于这些代码非常简单，所以不应该有边缘情况。
在这种环境下，如果你可以设置实际使用算术运算符来剥离整数的组成部分，那么可能是最好的。
例如
if (a & 16) becomes if ((a % 32) > 15)
a &= 16 becomes if ((a % 32) < 15) a += 16
如果您将RHS限制为2的恒定幂，那么这些运算符的转换足够明显。
剥掉两位或四位也很容易。
关于旧问题的一个不完整的答案，这里集中于AND，OR，XOR。 一旦找到这些按位操作之一的解决方案，就可以派生出其他两个。 有几种方法，其中一种在以下测试程序中显示（在gcc版本4.6.3（Ubuntu / Linaro 4.6.3-1ubuntu5）上编译）：
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#define XOR(a,b) (a + b - 2*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 errorn" );
if ( IOR(a,b) != (a|b) ) return printf( "IOR errorn" );
if ( XOR(a,b) != (a^b) ) return printf( "XOR errorn" );
} while ( ++b != 0 );
if ( (a & 0xff) == 0 )
fprintf( stderr, "." );
} while ( ++a != 0 );
return 0;
}
上一篇: Is it possible to implement bitwise operators using integer arithmetic?