使用mips汇编语言在整数中计数1(无任何控制指令流) [英] Counting 1's in an integer using mips assembly language (without any flow of control instructions)
问题描述
我目前正在开发一个程序,该程序以整数的二进制表示形式对1的数量进行计数,该整数由用户输入.我需要这样做,以便程序从上到下运行,这意味着没有循环或任何形式的指令流.但是,我对Mips和汇编语言非常陌生,并且目前正在为如何做到这一点而苦苦挣扎.
I am currently working on a program that counts the number of 1's in an integer's binary representation, where the integer is entered by the user. I need to do it so that the program runs from top down, so that means no loops or flow of instruction of any kind. However, I am very new to Mips and assembly language, and am currently struggling with how to do this.
我认为您可以使用srlv
和/或sllv
指令对此进行一些乘法运算,但是即使从哪里开始我也不知道.
I think that you can use the srlv
and/or sllv
instructions for this with some multiplication, but I have no clue even where to start.
推荐答案
您所描述的功能称为汉明重量.
The function you are describing is called the Hamming Weight.
我花了几秒钟的时间,浏览了Wikipedia文章此处,其中包含几种C算法计算汉明重量.我选择了这一点(将其略微更改为32位,并将常量移至函数中):
I took a couple seconds and looked at the Wikipedia article here which contains several C algorithms for computing Hamming Weight. I chose this one (changed slightly for 32 bits and moved constants to function):
//This uses fewer arithmetic operations than any other known
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
int popcount_3(uint32_t x) {
const uint32_t m1 = 0x55555555; //binary: 0101...
const uint32_t m2 = 0x33333333; //binary: 00110011..
const uint32_t m4 = 0x0f0f0f0f; //binary: 4 zeros, 4 ones ...
const uint32_t h01 = 0x01010101; //the sum of 256 to the power of 0,1,2,3...
x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
return (x * h01)>>24; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
在MIPS组件中,它看起来像:
In MIPS assembly this looks like:
main:
#read in int x for Hamming Weight
addi $v0 $zero 5
syscall
lui $t5 0x0101 #$t5 is 0x01010101
ori $t5 0x0101
lui $t6 0x5555 #$t6 is 0x55555555
ori $t6 0x5555
lui $t7 0x3333 #$t7 is 0x33333333
ori $t7 0x3333
lui $t8 0x0f0f #$t8 is 0x0f0f0f0f
ori $t8 0x0f0f
# x -= (x>>1) & 0x55555555
srl $t0 $v0 1
and $t0 $t0 $t6
sub $v0 $v0 $t0
# x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
and $t0 $v0 $t7
srl $t1 $v0 2
and $t1 $t1 $t7
add $v0 $t0 $t1
# x = (x + (x >> 4)) & 0x33333333
srl $t0 $v0 4
add $t0 $v0 $t0
and $v0 $t0 $t8
# output (x * 0x01010101) >> 24
mul $v0 $v0 $t5
srl $a0 $v0 24
li $v0 1
syscall
jr $ra
这篇关于使用mips汇编语言在整数中计数1(无任何控制指令流)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!