代码之家 › 专栏 › 技术社区 › Hristo

确定MIPS中数字的位表示的奇偶性

parity mips

Hristo · 技术社区 · 14 年前

MIPS中是否有一些指令将决定某一位表示的奇偶性?我知道确定一个“数字”是具有偶数奇偶校验还是奇数奇偶校验是将二进制表示的各个位异或在一起,但对于一组MIPS指令来说,这似乎需要大量的计算…我需要尽快完成。

另外,我工作的号码用灰色代码表示…把它扔进去。那么,MIPS中是否有一些伪指令来确定一个“数字”的奇偶性,或者我必须手工完成它?

如果没有MIPS指令(这似乎不太可能),有什么关于如何手工操作的建议吗?

谢谢, 希斯托

后续:我发现了一个优化,但我的实现不起作用。

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

1 回复 | 直到 14 年前

Matthew Slattery 14 年前

我不知道任何带有奇偶校验指令的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 “:
```
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}
```
(以及 结果 现在可以忽略;它们在计算的其余部分中没有任何有用的用途)。

在第二步之后,最下面的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{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条纯粹是寄存器操作的指令;它可能快,也可能不快。(这种微观优化总是需要分析!)