How to calculate how many bits in a decimal number is 1?

Question

This program I created in RISC-V RARS 1.3 application is designed to take a decimal number and count how many bits are in that number. The one I am testing is the decimal number 5, and this program should work for any positive number I put on t1. Here is the code I created. The program is meant to add one counter whenever the result of the AND function is not 0, but the problem I have is that the program does not stop. Is there a solution to this problem?

_start:

li t1,2 # start with decimal 5, binary 101
li t2,1 # adding counter for AND function
li t3,0 # bit counter count
li t4,0 # to compare 0

and t5,t1,t2 # t1 & t2 = t5
bne t5,t4,label # go to label if t5 != 0
beqz t5,label2 # go to label if t5 == 0

label:
addi t3,t3,1 # add one to bit count
slli t2,t2,1 # shift left
and t5,t1,t2 # t1 & new t2 = t5
bne t5,t4,label # go to label if t5 != 0
beqz t5,label2 # go to label if t5 == 0

label2:
slli t2,t2,1 # shift left
and t5,t1,t2 # t1 & new t2 = t5

.data

Answer 1

If RISC-V doesn't have an instruction that counts the number of set bits efficiently (most other CPUs do now); then the next best approach is like:

    // Value is 32 pieces with 1 bit per piece

    temp1 = (value & 0x555555555) + (value & 0xAAAAAAAA) >> 1;

    // Temp1 is 16 pieces with 2 bits per piece

    temp2 = (temp1 & 0x33333333) + (temp1 & 0xCCCCCCCC) >> 2;

    // Temp2 is 8 pieces with 4 bits per piece

    temp3 = (temp2 & 0x0F0F0F0F) + (temp2 & 0xF0F0F0F0) >> 4;

    // Temp3 is 4 pieces with 8 bits per piece

    temp4 = (temp3 & 0x00FF00FF) + (temp3 & 0xFF00FF00) >> 8;

    // Temp4 is 2 pieces with 16 bits per piece

    result = (temp4 & 0x0000FFFF) + (temp2 & 0xFFFF0000) >> 16;

    // Result is the count of all bits that were set in value (or, sum of all 32 of the original 1-bit values)

I have no idea how to write this in RISC-V assembly (I'd compile it then cut&paste the resulting assembly, but don't have a compiler for RISC-V either).

Answer 2

Since you start with t2 = 1 and multiply it by 2 in each iteration, you should stop the calculation once the value of t2 becomes greater than t1.

Also, in your code, I see you that you probably intended to handle two cases:

1. label: - this block handles the case when the current bit tested is 1, it increments the number of bits and then jumps to either label or label2. Here, you just need to add the exit condition as mentioned above
2. label2: - this block handles the case when the current bit tested is 0, it does not change the number of bits, but it also does not seem to continue with either label or label2. I think that is should keep looking whether there are any higher 1 bits, until the exit condition t2>t1 is reached.