Bestimmung einer Parität-Bit-Darstellung einer Zahl in MIPS

Question

Gibt es eine Anweisung in MIPS, die die Parität einer bestimmten Bit-Darstellung bestimmen? Ich weiß, um zu bestimmen, ob eine „Nummer“ eine gerade Parität oder eine ungerade Parität XOR die einzelnen Bits der binären Darstellung zusammen, aber das scheint rechenintensiv für eine Reihe von MIPS Anweisungen ... und ich brauche, dies zu tun so schnell wie möglich.

Auch die Zahl ich arbeite in Gray-Code dargestellt wird ... nur, dass werfen dort. So gibt es einige Pseudobefehl in MIPS die Parität einer „Nummer“, um zu bestimmen, oder muss ich es von Hand zu tun?

Wenn es keine MIPS-Befehls, die es sehr unwahrscheinlich scheint zu sein, irgendwelche Ratschläge, wie man es von Hand zu tun?

Danke, Hristo

Follow-up. I eine Optimierung gefunden, aber meine Implementierung arbeitet nicht

unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;

Answer 1

Ich bin nicht bekannt, dass MIPS Variante mit einer Parität Anweisung, aber es ist ein bisschen-twiddling Trick Parität schneller als die offensichtliche Methode zur Berechnung der wiederum durch jedes der 32 Bit ausgeführt wird. In C:

result = in ^ (in >> 16);
result ^= (result >> 8);
result ^= (result >> 4);
result ^= (result >> 2);
result ^= (result >> 1);
result &= 1;

• Nach dem ersten Schritt werden die unteren 16 Bits des Ergebnisses enthalten, um die Parität von Bits N und N + 16 der Eingangs - Wesentlichen 16 Schritten der Paritätsberechnung sind in einem Arbeitsgang durchgeführt worden ist. Schreiben result{N} bedeuten "Bit N von result":

  result{0}  =  in{0} ^ in{16}
  result{1}  =  in{1} ^ in{17}
  result{2}  =  in{2} ^ in{18}
  ...
  result{7}  =  in{7} ^ in{23}
  result{8}  =  in{8} ^ in{24}
  ...
  result{15} = in{15} ^ in{31}
  

  (und die restlichen Top-16-Bit result jetzt ignoriert werden kann; sie keinen nützlichen Zweck in dem Rest der Berechnung dienen).

• Nach dem zweiten Schritt werden die unteren 8 Bits des result enthalten die Parität von Bits N, N + 8, N + 16, + 24 N des ursprünglichen Eingangs:

  result{0} = result{0} ^ result{8}  =  in{0} ^  in{8} ^ in{16} ^ in{24}
  result{1} = result{1} ^ result{9}  =  in{1} ^  in{9} ^ in{17} ^ in{25}
  ...
  result{7} = result{7} ^ result{15} =  in{7} ^ in{15} ^ in{23} ^ in{31}
  

  (und wieder, können die verbleibenden Bits von hier an ignoriert werden).

• ... und so weiter, bis die Parität aller Bits der ursprünglichen Eingangsende in der unteren Bit result bis:

  result{0} = in{0} ^ in{1} ^ in{2} ^ ... ^ in{30} ^ in{31}
  

Dies ist einfach direkt Montage auf MIPS zu übersetzen; es ist 11 Anweisungen:

# input in $a0, output in $v0, $t0 corrupted
srl $t0, $a0, 16
xor $v0, $a0, $t0
srl $t0, $v0, 8
xor $v0, $v0, $t0
srl $t0, $v0, 4
xor $v0, $v0, $t0
srl $t0, $v0, 2
xor $v0, $v0, $t0
srl $t0, $v0, 1
xor $v0, $v0, $t0
and $v0, $v0, 1

---

Eine mögliche Verbesserung könnte sein, eine Lookup-Tabelle zu verwenden. Zum Beispiel, nach den ersten beiden Schritten, die wir haben:

    result{0} =  in{0} ^  in{8} ^ in{16} ^ in{24}
    result{1} =  in{1} ^  in{9} ^ in{17} ^ in{25}
    ...
    result{7} =  in{7} ^ in{15} ^ in{23} ^ in{31}

so konnten wir eine 256-Byte-Lookup-Tabelle an dieser Stelle verwenden. In C:

result = in ^ (in >> 16);
result ^= (result >> 8);
result = lookup_table[result & 0xff];

wo lookup_table[n] wurde vorberechnet, z.

for (i = 0; i < 256; i++) {
    n = i ^ (i >> 4);
    n ^= (n >> 2);
    n ^= (n >> 1);
    lookup_table[i] = n & 1;
}

Dies ist 7 MIPS Anweisungen, nicht mitgerechnet die Lookup-Tabelle Basisadresse in ein Register geladen:

# input in $a0, lookup table address in $a1, output in $v0, $t0 corrupted
srl  $t0, $a0, 16
xor  $v0, $a0, $t0
srl  $t0, $v0, 8
xor  $v0, $v0, $t0
andi $v0, $v0, 0xff
addu $t0, $a1, $v0
lbu  $v0, 0($t0)

Dies ist jedoch 7-Anweisungen, die einen Speicherzugriff enthalten, im Vergleich zu 11 Befehle, die Operationen sind rein registrieren; es kann oder auch nicht schneller sein. (Diese Art von Mikro-Optimierung muss immer profiliert werden!)