代码之家 › 专栏 › 技术社区 › Statement

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

compiler-optimization discrete-mathematics bitwise-operators

Statement · 技术社区 · 14 年前

我正面临一个相当奇怪的问题。我正在为一个不支持位操作的体系结构编写编译器。但是,它处理有符号16位整数运算,我想知道是否有可能只使用:

加法 ( )
( c=a-b
分部 ( c=a/b )
乘法 *
( )
最小值 ( )
(
( c=(a<b) ,c=(a==b),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;

位移位 可以表示为:

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

或一套&跳跃进近:

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

6 回复 | 直到 5 年前

phuclv 10 年前

移位的第一个解决方案(移位是移位距离,不能为负,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;
}

EDIT:我实际测试了所有可能的操作数值(-32768到32767)在0到31之间的移位的正确性,它工作正常(假设整数除法)。对于AND/OR/XOR代码,在我的机器上进行详尽的测试花费的时间太长,但是由于这些代码非常简单,因此无论如何都不应该有边缘情况。

Joshua 14 年前

在这种环境中,最好是设置为实际使用算术运算符来剥离整数的组件。

例如。

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

如果将RHS限制为2的常数幂,这些运算符的变换就足够明显了。

phuclv 5 年前

一个老问题的不完整答案,这里集中在AND,OR,XOR上。一旦这些位运算中的一个找到了解,就可以导出另外两个。有几种方法,其中一种在下面的测试程序中显示(在gcc版本4.6.3(Ubuntu/linaro4.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;
}

phuclv 5 年前

你可以一点一点地操作(就像markbyers建议的那样),通过提取每一个缓慢的位。

或者您可以加快处理速度,并使用二维查找表来存储结果,例如,两个4位操作数的结果并对其进行操作。你将需要更少的提取比如果你是位操作。

可以使用宏将每个按位操作展开为如下内容:

/*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个变量来实现这个。

每一个位操作都将围绕类似于 AND_MACRO -将a和b的剩余值与“mask”(即“c”参数)进行比较。然后将mask添加到if分支中适合您操作的结果中。如果设置了位,则从值中减去掩码。

根据您的平台,它可能比使用%和/提取每一位,然后使用乘法将其放回要快。

phuclv 5 年前

只要你愿意它非常昂贵,是的。

基本上,您将显式地将一个数字放入以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]  ;
  }
}

phuclv 5 年前

只是一些其他的方法

16位和

int and(int a, int b) {
    int d=0x8000;
    int result=0;
    while (d>0)  {
        if (a>=d && b>=d) result+=d;
        if (a>=d) a-=d;
        if (b>=d) b-=d;
        d/=2;
    }
    return result;
}

双重的 2位和

int and(int a, int b) {
    double x=a*b/12;
    return (int) (4*(sign(ceil(tan(50*x)))/6+x));
}

32位整数 2位和

int and(int a, int b) {
    return ((684720128*a*a -b) * a) % (b+1);
}

16位整数 解决方案 2位和

int and(int a, int b) {
    return ((121 * a) % 16) % (b+1);
}

16位整数 解决方案 :

int and(int a, int b) {
    return sign(a) * ((((-23-a) * (40+b)) % 2)+40+b) % ((10624 * ((((-23-a) * (40+b))%2)+40+b)) % (a%2 - 2 -a) - a%2 + 2 +a);
}