определить четность битового представления числа в MIPS

Я не знаю ни одного варианта 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} для обозначения "бит 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}
  

  (а оставшиеся 16 старших бит result теперь можно игнорировать; они не служат никакой полезной цели в оставшейся части вычислений).

• После второго шага нижние 8 бит result содержат биты четности 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 инструкциями, которые являются чисто регистровыми операциями; это может быть или не быть быстрее. (Такого рода микрооптимизация всегда требует профилирования!)