Bit Difference between 2 binary numbers in MIPS Assembly

Question

So I have to create an MIPS assembly program that reads 2 numbers out of 2 registers ($s0 & $s1) and calculates the number of bits that these 2 numbers differ by. And stores the result in the $s2 register. I also have to fulfill all the above with the least amount of commands possible. I have tried a few things on paper with XOR operations but I can't quite figure how to calculate the amount of different bits.

If anyone can help, you're more than welcome to. Thanks in advance

Answer 1

XOR the bits together and then count the number of bits in the resulting number. To do that, you can loop over each bit, check if it is set (by using a bitmask and bitshift), and then increment a counter.

I am purposefully leaving this vague as this is for you to figure out.

Answer 2

Here is a way that avoids looping over the 32 bits. It repetitively clears all bits, but the left most one, while counting their number.

  // 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
  }

It is based on the well known property that x&-x is equal to the lower weight set bit in x.

The inner loop requires 5 mips instructions.

Answer 3

Example in C using loopless pop count code:

    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