確定MIPS中數字的位表示的奇偶校驗

Question

MIPS中是否有一些指令會確定某個位表示的奇偶校驗？我知道要確定一個「數字」是否具有偶數奇偶性，或者奇數奇偶性是否將二進制表示的各個位異或以異或，但對於一組MIPS指令而言這似乎是計算密集型的......我需要這樣做盡可能快。

此外，我正在工作的電話號碼以格雷碼錶示...只是爲了將其放在那裏。那麼MIPS中是否存在一些僞指令來確定「數字」的奇偶性還是我必須手動完成？

如果沒有看起來不太可能的MIPS指令，有關如何手工完成的任何建議？

感謝， 斯托伊奇

後續：我發現了一個優化的，但我的實現不工作。

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

Answer 1

我不知道任何MIPS變種具有奇偶指令，但有計算奇偶比通過每個又將32位的運行的方法明顯快位變換伎倆。在C：

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

• 在第一步驟之後，結果的低16位包含的位的n個奇偶校驗和N的輸入的+ 16 - 本質上，奇偶校驗計算的16個步驟已經執行一氣呵成。寫入result{N}意味着「的result位N」：

  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} 
  

  （和result剩餘高16位現在可以忽略;它們用於在該計算的其餘部分沒有有用的目的）。

• 在第二步驟之後，的result底部8位包含比特N，N + 8，N + 16的奇偶校驗，與原始輸入的N + 24：

  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} 
  

  （並再次，從這裏開始可以忽略其餘的位）。

• ...等，直到原始輸入的所有位的奇偶性在result底位結束：

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

這是很容易直接轉化爲MIPS部件;這11個指令：

# 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 

---

一個可能的改進可能是使用的查找表。例如，在前兩個步驟後，我們有：

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} 

所以我們可以在這一點上使用一個256字節的查找表。在C：

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

其中lookup_table[n]已預先計算，例如：

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

這是7個MIPS指令，不計算加載查找表基址到寄存器：

# 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) 

然而，這是7級的指令包括存儲器存取，與11級的指令是純粹註冊操作;它可能會或可能不會更快。 （這種微優化總是需要分析！）