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.