Is it possible to implement bitwise operators using integer arithmetic?

Question

Hello World!

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

Answer 1

In this environment it might be best if you could set up to actually use arithmatic operators to peel out components of integers.

E.G.

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

The transforms for these operators are obvious enough if you restrict RHS to a constant power of 2.

Peeling off two or four bits is also easy to do.

Answer 2

You can operate bit-by-bit (as Mark Byers suggested), by extracing every bit which will be slow.

Or you could accelerate process and use 2d lookup tables that store results, say, for two 4-bit operands and operate on those. You'll need less extractions than if you were operating on bits.

YOu can also do everything using addition, substraction and >= operation. Every bitwise operation can be unrolled into something like this using 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;
}

You'll need 3 variables to implement this.

Every bitwise operation will revolve around macros similar to AND_MACRO - you compare remaining values of a and b to the "mask" (which is "c" parameter). then add mask to the result in the if branch that is suitable for your operation. And you subtract mask from values, if bit is set.

Depending on your platform, it may be faster than extracting every bit using % and / , and then putting it back using multiplication.

See for yourself whichever is better for you.

Answer 3

As long as you're willing for it to be very expensive, yes.

Basically, you'll explicitly put a number into a base-2 representation. You do this just as you would put a number into base-10 (e.g., to print it out), that is, by repeated division.

This turns your number into an array of bools (or ints in the range 0,1), then we add functions to operate on those arrays.

again, not that this is tremendously more expensive than bitwise operations, and that almost any architecture will supply bitwise operators.

In C (of course, in C you have bitwise operators, but...) an implementation might be:

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

Answer 4

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.