Counting the number of bits that are set

Question

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

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

Any ideas?

Thanks in advance for all the help.

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

Answer 1

What you're looking for is often referred to as the population count (popcount).

Are you looking for actual implementations, or are you just looking for ideas on how to do this quickly? There are a number of C implementations on Bit Twiddling Hacks here (some of which are scarily clever). If you're familiar with C, each approach should have a reasonable translation into MIPS assembly after breaking down the expressions.

If your input domain is small (e.g. 0-256), you could always do a lookup table and use the input as the offset to fetch the popcount directly.

Answer 2

Since this sounds like homework, I'm not going to give the MIPS code, but here's the algorithm (written in C). It should be straightforward to translate into 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

The link Chris gave gives some good methods for bit counting. I would suggest this method, as it is both very fast and doesn't require looping but only bit-wise operation, which would be easier to do in assembly.

Another way you might get the assembly code is to make the code in C, compile it and then look at the output assembly (most compiles can produce an assembly file output (-S for gcc, but make sure to disable optimization via -O0 to get easier to understand code), or allow you to view the binary file disassembled). It should point you in the right direction.

As an anecdote, I've done some testing a while back on PowerPC (not MIPS, I know...) for the quickest way to count bits in a 32 bit int. The method I linked was the best by far from all other methods, until I did a byte sized lookup table and addressed it 4 times. It would seem that the ALU is slower than referencing the cache (running around a million numbers through the algorithm).