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