确定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级的指令是纯粹注册操作;它可能会或可能不会更快。 （这种微优化总是需要分析！）