Best way to calculate number of 1's in the bin

问题:

I need to calculate the number of 1's in a binary number, lets say 5, so 00001001 would be 2 or n=2. I am using MIPS. Best way to do this?

回答1:

The best way to do this is to count them.

You can check if the least significant bit is set (a 1) by anding it with one. If you get a non-zero result, it was set, so you should increment a counter (that was originally initialised to zero of course).

You can shift all the bits of a value right by using logical shifty operators.

You can loop doing both those operations until your value ends up as zero. There are conditional branch instructions in most architectures.

Your task, then, is to find those instructions for MIPS and put them in the correct order :-)

In no particular order, I'd be looking into the following set of instructions: {andi, srl, beq, addi}, though there may be a few others you'll need.