Ist es möglich, bitweise Operatoren mit ganzzahliger Arithmetik zu implementieren?

Question

Ich stehe vor einem recht merkwürdigen Problem. Ich arbeite an einem Compiler für eine Architektur, die keine bitweisen Operationen unterstützt. Er verarbeitet jedoch vorzeichenbehaftete 16-Bit-Integer-Arithmetik, und ich frage mich, ob es möglich wäre, bitweise Operationen zu implementieren, indem ich nur:

• Zusatz ( c = a + b )
• Subtraktion ( c = a - b )
• Abteilung ( c = a / b )
• Multiplikation ( c = a * b )
• Modulus ( c = a % b )
• Minimum ( c = min(a, b) )
• Maximum ( c = max(a, b) )
• Vergleiche ( c = (a < b), c = (a == b), c = (a <= b), usw. )
• Sprünge ( goto, for, et.c. )

Die bitweisen Operationen, die ich unterstützen möchte, sind:

• Oder ( c = a | b )
• Und ( c = a & b )
• Xoder ( c = a ^ b )
• Linksverschiebung ( c = a << b )
• Rechtsverschiebung ( c = a >> b )
• (Alle Ganzzahlen sind vorzeichenbehaftet, daher ist dies ein Problem)
• Unterzeichnete Schicht ( c = a >>> b )
• Die eigene Ergänzung ( a = ~b )
• (Ich habe bereits eine Lösung gefunden, siehe unten)

Normalerweise ist das Problem genau andersherum, nämlich wie man arithmetische Optimierungen mit bitweisen Hacks erreicht. In diesem Fall jedoch nicht.

Beschreibbarer Speicher ist sehr knapp auf dieser Architektur, daher der Bedarf an bitweisen Operationen. Die bitweisen Funktionen selbst sollten nicht viele temporäre Variablen verwenden. Konstanter Nur-Lese-Speicher für Daten und Anweisungen ist jedoch reichlich vorhanden. Eine Randbemerkung ist auch, dass Sprünge und Verzweigungen nicht teuer sind und alle Daten leicht zwischengespeichert werden können. Sprünge kosten nur halb so viele Zyklen wie arithmetische Befehle (einschließlich Laden/Speichern). Mit anderen Worten: Alle oben genannten unterstützten Funktionen kosten doppelt so viele Zyklen wie ein einzelner Sprung.

---

Einige Gedanken, die helfen könnten:

Ich habe herausgefunden, dass man Folgendes tun kann Komplementärstück (Bits negieren) mit folgendem Code:

// Bitwise one's complement
b = ~a;
// Arithmetic one's complement
b = -1 - a;

Ich erinnere mich auch an den alten Shift-Hack beim Dividieren durch eine Zweierpotenz, so dass die Bitweise Verschiebung kann wie folgt ausgedrückt werden:

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

Für den Rest der bitweisen Operationen bin ich etwas ratlos. Ich wünschte, die Architekten dieser Architektur hätten Bit-Operationen vorgesehen.

Ich würde auch gerne wissen, ob es einen schnellen/einfachen Weg gibt, die Zweierpotenz (für Verschiebeoperationen) zu berechnen, ohne eine Speicherdatentabelle zu verwenden. Eine naive Lösung wäre, in ein Feld von Multiplikationen zu springen:

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

Oder ein Set & Jump-Ansatz:

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