使用整数算术可以实现按位运算符吗？
我面临一个相当奇怪的问题。 我正在编写一个不支持按位操作的体系结构的编译器。 然而，它处理有符号的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. ）
- 跳转 （ 跳转，等等 ）
我希望能够支持的按位运算是：
- 或者 （ c = a | b ）
- 和 （ c = a＆b ）
- XOR （ C = A ^ B ）
- 左移 （ c = a << b ）
- 右移 （ c = a >> b ）
- （所有的整数都被签名，所以这是一个问题）
- 签字转换 （ c = a >>> b ）
- 补的 （ a =〜b ）
- （已经find了解决办法，见下文）
通常这个问题是相反的; 如何使用按位黑客来实现算术优化。 但是不是在这种情况下。
可写内存在这个架构上非常稀缺 ，因此需要按位操作。 按位函数本身不应该使用大量的临时variables。 但是，恒定的只读数据和指令存储器是丰富的。 这里还要注意的一点是，跳转和分支并不昂贵，并且所有的数据都很容易被caching。 算术（包括加载/存储）指令所做的跳转花费了一半的周期。 换句话说，上述所有支持的函数都要花费两次单跳的周期。
有些想法可能有帮助：
我发现你可以用下面的代码做补码 （否定位）：
// 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;
对于其他的按位操作，我有点无知。 我希望这个架构的架构师能够提供位操作。
我也想知道，如果没有使用内存数据表，是否有一种快速/简单的方式来计算两个function（用于移位操作）。 一个天真的解决办法是跳进一个乘法的领域：
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; }
第一个移位解决scheme（移位是移位距离，不能是负数，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，我不能想出一个简单的解决scheme，所以我会做循环每个单一的位。 可能有更好的办法来做到这一点。 伪代码假定a和b是input操作数，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; }
那就是假设所有的variables都是16位的，所有的操作都是有符号的（所以当bit 15被设置时，<0实际上是真的）。
编辑：我实际上testing了所有可能的操作数值（-32768到32767）的范围从0到31的正确性，并正常工作（假设整数除数）。 对于AND / OR / XOR代码，彻底的testing在我的机器上花费的时间太长，但是因为这些代码非常简单，所以不应该有边界情况。
在这种环境下，如果你可以设置实际使用算术运算符来剥离整数的成分，那么可能是最好的。
例如
if (a & 16) becomes if ((a % 32) > 15) a &= 16 becomes if ((a % 32) < 15) a += 16
如果将RHS限制为2的恒定幂，那么这些运算符的转换就足够明显了。
剥掉两位或四位也很容易做到。
在一个老问题上的不完整的答案，这里集中在AND，OR，XOR。 一旦find这些按位操作之一的解决scheme，就可以派生出另外两个。 有几种方法，一个在下面的testing程序（在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 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; }
你可以逐位进行操作（就像马克·拜尔斯（Mark Byers）所build议的那样），通过提取每一个缓慢的位。
或者，您可以加速进程，并使用2d查找表来存储结果，例如，对于两个4位操作数并对其进行操作。 与使用位数相比，您将需要更less的提取。
YOu也可以使用加法，减法和> =操作来完成所有的事情。 每个按位操作都可以使用macros展开成这样的东西：
/*I didn't actually compile/test it, it is just illustration for the idea*/ uint16 and(uint16 a, uint16 b){ uint16 result = 0; #define AND_MACRO(c) \ if (a >= c){ \ if (b >= c){\ result += c;\ b -= c;\ }\ a -= c;\ }\ else if (b >= c)\ b -= c; AND_MACRO(0x8000) AND_MACRO(0x4000) AND_MACRO(0x2000) AND_MACRO(0x1000) AND_MACRO(0x0800) AND_MACRO(0x0400) AND_MACRO(0x0200) AND_MACRO(0x0100) AND_MACRO(0x0080) AND_MACRO(0x0040) AND_MACRO(0x0020) AND_MACRO(0x0010) AND_MACRO(0x0008) AND_MACRO(0x0004) AND_MACRO(0x0002) AND_MACRO(0x0001) #undef AND_MACRO return result; }
你需要3个variables来实现这个。
每个按位操作都将围绕类似于AND_MACRO的macros进行 – 将a和b的剩余值与“掩码”（即“c”参数）进行比较。 然后将掩码添加到适合您操作的if分支中的结果。 如果设置了位，则从值中减去掩码。
根据您的平台，它可能比使用％和/来提取每一位更快，然后使用乘法将其放回。
自己看看哪个更适合你。
只要你愿意，它是非常昂贵的，是的。
基本上，你会明确地把一个数字放入一个基数2的表示。 你这样做，就像你将一个数字放到10（例如打印出来）一样，也就是说，通过重复的划分。
这将您的数字转换为布尔数组（或范围为0,1的整数），然后我们添加函数来操作这些数组。
而且这并不是说这比按位操作要贵得多，几乎所有的架构都会提供按位运算符。
在C中（当然，在C中你有按位运算符，但是…）实现可能是：
include <limits.h> const int BITWIDTH = CHAR_BIT; typedef int[BITWIDTH] bitpattern; // fill bitpattern with base-2 representation of n // we used an lsb-first (little-endian) representation void base2(char n, bitpattern array) { for( int i = 0 ; i < BITWIDTH ; ++i ) { array[i] = n % 2 ; n /= 2 ; } } void bitand( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = op1[i] * op2[i]; } } void bitor( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = (op1[i] + op2[i] != 0 ); } } // assumes compiler-supplied bool to int conversion void bitxor( bitpattern op1, bitpattern op2, bitpattern result ) { for( int i = 0 ; i < BITWIDTH ; ++i ) { result[i] = op1[i] != op2[i] ; } }
