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
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.
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.
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
