使用整数算术可以实现按位运算符吗?

我面临一个相当奇怪的问题。 我正在编写一个不支持按位操作的体系结构的编译器。 然而,它处理有符号的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
  • XORC = 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; } 

5 Solutions collect form web for “使用整数算术可以实现按位运算符吗?”

第一个移位解决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] ; } } 
  • 计算两点之间的最短路线
  • 我如何四舍五入到最接近的0.5?
  • 为什么Math.floor返回一个double?
  • 如何处理Java BigDecimal的性能?
  • log2在Pythonmath模块
  • 不要在情节轴上使用科学记数法
  • MATLAB函数中的可选参数
  • 我怎样才能把LaTeX与Markdown混合?
  • 为什么在反向传播neural network中必须使用非线性激活函数?
  • 从一个旋转的矩形计算边界框坐标
  • 绕一个点旋转一步仿射变换?