是否可以使用整数算术实现按位运算符？ [英] Is it possible to implement bitwise operators using integer arithmetic?

问题描述

我正面临一个非常特殊的问题。我正在为不支持按位运算的体系结构编写编译器。但是，它处理有符号的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），等等。）


• 跳转（转到，等。）

我想支持的按位运算是：

• Or （ c = a | b ）


• 和（ c = a& b ）


• 异或（ c = a ^ b ）


• 左移 （ c = a<< b ）


• 右移（ c = a >> b ）


• （所有整数都有符号，所以这是个问题）


• 有符号移位（ c = a >>> b ）


• 一个人的补语（ a =〜b ）


• （已找到解决方案，请参见

通常问题是相反的；如何使用按位黑客实现算术优化。但是在这种情况下不是。

在这种体系结构上，可写内存非常稀缺，因此需要按位操作。按位函数本身不应使用大量临时变量。但是，恒定的只读数据&指令存储器丰富。这里的另一个注释是跳转和分支并不昂贵，并且所有数据都易于缓存。跳转的花费是算术（包括加载/存储）指令的一半周期。换句话说，以上所有受支持的功能的成本都是单次跳转的两倍。

---

有些想法可能会有所帮助：

我发现您可以使用以下代码进行补码（取反位）：

  //按位补码
b =〜a; 
 //算术补数
 b = -1-a; 
  

我还记得除数为2时的旧移位技巧，因此按位移位可以表示为：

  //按位左移
b = << 4; 
 //算术左移
 b = a * 16; // 2 ^ 4 = 16 
 
 //有符号右移
 b = a>>> 4; 
 //算术右移
 b = a / 16; 
  

对于其余的按位操作，我一点都不了解。我希望这种体系结构的架构师能够提供位操作。

我还想知道是否有快速/简便的方法来计算两个幂（用于移位操作），而无需使用内存数据表。一个幼稚的解决方案是跳到乘法领域：

  b = 1; 
开关（a）
 {
情况15：b = b * 2； 
情况14：b = b * 2； 
 // ...探索失败（指令内存更大）
情况2：b = b * 2; 
情况1：b = b * 2； 
} 
  

或集合&跳转方法：

 开关（a）
 {
案例15： b = 32768；打破; 
情况14：b = 16384;打破; 
 // ...利用了这样的事实，即跳转比另外一个mul 
 //快，但其代价是指令存储器占用空间增加了一倍。 
情况2：b = 4；打破; 
情况1：b = 2；打破; 
} 
  

解决方案

第一个解决方案（shift是移位距离，不能为负，a是要移位的操作数，完成后还包含结果）。功率表由所有三个移位操作使用。

  //用于移位操作的表
 powtab = {1，2，4，4，8，16，32，64，128，256，512，1024，2048，4096，8192，16384，-32768}; 
 
 //如果（shift> 15）{
 a = 0; //如果向左移动15位以上，则值始终为零
}否则{
 a * = powtab [shift]; 
} 
 
 //逻辑右移（无符号）
 if（shift> 15）{
 a = 0; //大于15，则变为零
}否则，如果（shift> 0）{
 if（a< 0）{
 //处理符号位（15）
a + = -32768; 
 a / = powtab [shift]; 
 a + = powtab [15-shift]; 
} else {
 a / = powtab [shift]; 
} 
} 
 
 //算术右移（有符号）
 if（shift> = 15）{
 if（a< 0） {
a = -1; 
} else {
 a = 0; 
} 
} else if（shift> 0）{
 if（a< 0）{
 //处理符号位
a + = -32768 ; 
 a / = powtab [shift]; 
 a-= powtab [15-shift]; 
} else {
 //与无符号移位相同
 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; 
} 
}否则，如果（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; 
} 
 
 //或（|）
 c = 0; 
 for（x = 0; x< = 15; ++ x）{
 c + = c; 
 if（a< 0）{
 c + = 1; 
}否则，如果（b< 0）{
 c + = 1; 
} 
 a + = a; 
 b + = b; 
} 
  $$$$ a<当位15设置时实际上为0）。
 
 
 
编辑：我实际上测试了所有可能的操作数值（-32768至32767），范围从0到31以确保正确性，并且可以正常工作（假设整数除法）。对于AND / OR / XOR代码，详尽的测试在我的计算机上花费的时间太长，但是由于这些代码非常简单，因此无论如何都不应存在边缘情况。
 
I am facing a rather peculiar problem. I am working on a compiler for an architecture that doesn't support bitwise operations. However, it handles signed 16-bit integer arithmetics and I was wondering if it would be possible to implement bitwise operations using only: 


Addition (c = a + b)
Subtraction (c = a - b)
Division (c = a / b)
Multiplication (c = a * b)
Modulus (c = a % b)
Minimum (c = min(a, b))
Maximum (c = max(a, b))
Comparisons (c = (a < b), c = (a == b), c = (a <= b), et.c.)
Jumps (goto, for, et.c.)


The bitwise operations I want to be able to support are:


Or (c = a | b)
And (c = a & b)
Xor (c = a ^ b)
Left Shift (c = a << b)
Right Shift (c = a >> b) 
(All integers are signed so this is a problem)
Signed Shift (c = a >>> b)
One's Complement (a = ~b)
(Already found a solution, see below)


Normally the problem is the other way around; how to achieve arithmetic optimizations using bitwise hacks. However not in this case.

Writable memory is very scarce on this architecture, hence the need for bitwise operations. The bitwise functions themselves should not use a lot of temporary variables. However, constant read-only data & instruction memory is abundant. A side note here also is that jumps and branches are not expensive and all data is readily cached. Jumps cost half the cycles as arithmetic (including load/store) instructions do. On other words, all of the above supported functions cost twice the cycles of a single jump.



Some thoughts that might help:

I figured out that you can do one's complement (negate bits) with the following code:
// Bitwise one's complement
b = ~a;
// Arithmetic one's complement
b = -1 - a;
I also remember the old shift hack when dividing with a power of two so the bitwise shift can be expressed as:
// 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;
For the rest of the bitwise operations I am slightly clueless. I wish the architects of this architecture would have supplied bit-operations.

I would also like to know if there is a fast/easy way of computing the power of two (for shift operations) without using a memory data table. A naive solution would be to jump into a field of multiplications:
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;
}
Or a Set & Jump approach:
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;
}

解决方案
First solutions for shifting (shift is the shift distance, must not be negative, a is the operand to be shifted and contains also the result when done). The power table is used by all three shift operations.
// 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];
    }
}
For AND, OR and XOR i could not come up with a simple solution, so i'll do it with looping over each single bit. There might be a better trick to do this. Pseudocode assumes a and b are input operands, c is the result value, x is the loop counter (each loop must run exactly 16 times):
// 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;
}
Thats assuming that all variables are 16 bits and all operations behave as signed (so a<0 actually is true when bit 15 is set).

EDIT: i actually tested all possible operand values (-32768 to 32767) for shifts ranging from 0 to 31 for correctness and it works correctly (assuming integer divides). For the AND/OR/XOR code an exhaustive test takes too long on my machine, but since the code for these is pretty simple there should be no edge cases anyway.

                        
这篇关于是否可以使用整数算术实现按位运算符？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！