Home > Back-end >  MIPS Assembly converting integer to binary and reading the number of 1's?
MIPS Assembly converting integer to binary and reading the number of 1's?

Time:03-15

I am working on a program that takes an integer from the user and then outputs how many 1's there are in it's binary equivalent. So first I believe I need to convert it to binary and then use a loop and check all 32 bits to find how many 1's there are.

I have been browsing around for hours and trying different things to first convert the integer to binary. What's the best way to do this? Is there a way to to read a register value in binary directly, or do I need to convert it first? This is all the code I have so far.

  .data
EnterInteger: .asciiz "Enter an integer: "


.text
 # Print the first message
 li $v0, 4
 la $a0, EnterInteger
 syscall

 # Prompt the user to enter the first integer
 li $v0, 5
 syscall

 # Store the first integer in $t0
 move $t0, $v0

Here is the code I have so far but it's not working. When I input 4673 I should get "4", instead I only get "1"

    .data
Msg: .asciiz "Enter an integer: "



.text
 # Print the first message
 li $v0, 4
 la $a0, Msg
 syscall

 # Prompt the user to enter the first integer
 li $v0, 5
 syscall

 # Store the first integer in $t0
 move $t0, $v0

 addi $t3, $zero, 0

main:
 bgt $t3, 32, exit
 andi $t0, $v0, 1
 bne $t0, $zero, count 
 



count:
 addi $t3, $t3, 1
 addi, $t1, $zero, 1
 # Shift to the next bit and then go back to main
 srl $t0, $t0, 1
 j main
 
exit:

# Tell the interpreter to get read to print an integer
 li $v0, 1
 add $a0, $zero, $t1
 
 #Print the integer
 syscall
 
 # End the program
 li $v0, 10
 syscall

CodePudding user response:

As Michael commented, integers in registers are already in binary. A register is a group of 32 bits.

Crucially, operations on registers like andi $t1, $v0, 1 and srl $v0, $v0, 1 work in binary. i.e. the resulting 0 or 1 from and is the value mod 2, and right-shift by 1 place divides by 2.

This is a consequence of MIPS being a binary computer, like every over real-world ISA you might learn assembly for. Higher-level languages including C, Java, and Python that have & and >> operations also always guarantee that they work in binary. (On a non-binary computer, e.g. ternary, implementing those semantics for x & y would involve converting to an array of base-2 digits and doing the logic manually, then converting back.)

If you want to work with other number bases, like base 10, you'd need to do actual division (MIPS divu) or remainder to remove or isolate the lowest base-10 digit. Or if the base is a power of 2, like base 16, then shift by 4 bits, or AND with 0x0f (take the low 4 bits, i.e. 0b1111).


Input / output in other bases involves converting (binary) integers from / to strings of ASCII digits representing digits in another base. The MARS/SPIM read_int call (syscall with $v0 = 5) does that for you, like C library functions scanf or printf. To do it manually, you do stuff like total = total * 10 digit, where digit is something like ascii_char - '0'. Or for output, repeated division / modulo by 10 to get the base-10 digits, starting with the lowest.

There are some MIPS Q&As about manually converting to/from strings, but not many because most students using MIPS are using MARS or SPIM with their toy system calls that do things normally done by a C library, or by hand. But IIRC there are some if you search.

ASCII decimal or hex strings are a serialization format for numbers, not how they exist inside computers (except as strings, not integers).


Popcount

Looping over the bits one at a time, extracting and adding the low bit, is a simple but often inefficient way to count the number of set bits. Still, simple is good for a first attempt; the choice of andi and srl as examples earlier is a hint.

Some faster bithacks are shown on How to count the number of set bits in a 32-bit integer? although for MIPS that means generating lots of separate 32-bit constants which cost 2 instructions each. You could do two SWAR widening steps and then loop over groups of 4-bit sums, as a middle ground.

Count bits 1 on an integer as fast as GCC __builtin__popcount(int) shows a way where you count iterations of n &= n-1 to clear the lowest set bit, which is faster if there are only a few bits set, even if they're not near the bottom of the register.

  • Related