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.

Pennate

Answer 1

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

There are a number of C implementations on Bit Twiddling Hacks (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-255), you could always do a lookup table and use the input as the offset to fetch the popcount directly.

Submediant

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

Scramble

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

Pickerel

Answer 4

The easiest way to find out is to ask a compiler. There are several online compilers; the best one currently is godbolt (aka Compiler Explorer). For example, at https://godbolt.org/z/4ahfovr7z you can see the results of taking a simple bitcounting algorithm:

int pop_count(uint32_t in) {
  int count = 0;
  while (in) in &= in - 1, count += 1;
  return count;
}

and converting it to MIPS assembly, x86-64 assembly, and more recent x86-64 assembly. (I mention the latter only because this calculation is just a single instruction. Sadly, even with -march=mips64r6 there is no fast MIPS popcount, though there is a fast count of leading zeroes)

Robbegrillet

Answer 5

easy with loop in basic 32bit asm, guess this is the naive way, assuming you have print_eax fun:

start:

mov ebx, 97d

mov ecx, 32d

xor eax, eax

accumulate:

ror ebx,1

jnc continue

inc eax

continue:

loop accumulate

call print_eax

Olmstead

The question is tagged #mips. – Aflame

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Telemachus