Битовая разница между двумя двоичными числами в сборке MIPS

Поэтому мне нужно создать программу сборки MIPS, которая считывает 2 числа из 2 регистров ($s0 и $s1) и вычисляет количество битов, на которое различаются эти 2 числа. И сохраняет результат в регистре $s2. Я также должен выполнить все вышеперечисленное с наименьшим количеством возможных команд. Я пробовал несколько вещей на бумаге с операциями XOR, но я не могу понять, как рассчитать количество разных битов.

Если кто-то может помочь, добро пожаловать. заранее спасибо


assembly mips smips
person Spyros Giannikakis    schedule 29.05.2019    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Выполните операцию XOR над битами, а затем подсчитайте количество битов в полученном числе. Для этого вы можете перебрать каждый бит, проверить, установлен ли он (используя битовую маску и битовый сдвиг), а затем увеличить счетчик.

Я намеренно оставляю это расплывчатым, так как это для вас, чтобы понять.

person KaiJ    schedule 29.05.2019
comment
Сдвигайте столько раз, сколько ширина вашего регистра, и добавляйте ноль с переносом к другому - person 0___________; 29.05.2019

arrow_upward
0
arrow_downward

Вот способ избежать зацикливания 32 бит. Он многократно очищает все биты, кроме самого левого, при подсчете их количества.

  // x and y are the bits to compare
  int z=x^y;  // only bits different between x and y are set
  int w;
  int cnt=0;
  while(w=z&-z) { //w only has the left bit in z set
    cnt++;
    z^=w; // clear the processed bit
  }

Он основан на хорошо известном свойстве, что x&-x равно младшему биту веса в x.

Внутренний цикл требует инструкций 5 mips.

person Alain Merigot    schedule 29.05.2019
comment
Быстрее использовать идиому z &= z-1 для очистки самого младшего установленного бита, вместо того, чтобы фактически изолировать его и затем использовать XOR для его очистки. Всего 2 инструкции плюс приращение счетчика и bne. Итого 4 вместо 5. - person Peter Cordes; 30.05.2019

arrow_upward
0
arrow_downward

Пример на C с использованием кода счетчика всплывающих окон без петель:

    int x, y, z;
    // ...
    z = x^y;   // x and y are inputs
    z -= (z >> 1) & 0x55555555;                      // 16   2 bit counts
    z = (z & 0x33333333) + ((z >> 2) & 0x33333333);  //  8   4 bit counts
    z = (z + (z >> 4)) & 0x0f0f0f0f;                 //  4   8 bit counts
    z = (z * 0x01010101) >> 24;                      //  1  32 bit count
person rcgldr    schedule 29.05.2019