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

Question

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

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

Answer 1

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

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

Answer 2

Пример на 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

Answer 3

Вот способ, который позволяет избежать зацикливания на 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-ти миллиметровых инструкций.