Counting the number of bits set

Question

I want to count the number of bits in a binary number that is set. For example, the user enters number 97, which is 01100001 in binary format. The program should give me three bits to be set using MIPS ISA.

I can achieve this in C, but I don't know how to achieve it using assembly code.

Any ideas?

Thanks in advance for your help.

This is not HW, this is a tiny part of my research project.

Answer 1

What you are looking for is often referred to as a population count (popcount).

C Bit Twiddling Hacks ( ). C, MIPS .

(, 0-255), popcount.

Answer 2

, MIPS, ( C). MIPS:

int bits(unsigned int number)
{
    // clear the accumulator
    int accumulator = 0;
    // loop until our number is reduced to 0
    while (number != 0)
    {
        // add the LSB (rightmost bit) to our accumulator
        accumulator += number & 1;
        // shift the number one bit to the right so that a new
        // bit is in the LSB slot
        number >>= 1;
    }
    return accumulator;
}

Answer 3

, , . , , - , .

- C, , ( (-S gcc, -O0, ), ). .

As a joke, I tested PowerPC for some time (and not MIPS, I know ...) to quickly count bits in a 32-bit int. The method that I linked was the best of all the other methods until I ran the lookup table byte size and accessed it 4 times. It would seem that ALU is slower than cache binding (runs about a million numbers through the algorithm).