我想要统计一个二进制数字中被设置的位数。例如,用户输入数字97,它在二进制中表示为01100001。程序应该告诉我有3个位被设置了,使用MIPS ISA。
我能够在C中实现这个功能,但不知道如何使用汇编代码实现。
我想要统计一个二进制数字中被设置的位数。例如,用户输入数字97,它在二进制中表示为01100001。程序应该告诉我有3个位被设置了,使用MIPS ISA。
我能够在C中实现这个功能,但不知道如何使用汇编代码实现。
由于这听起来像是一道作业题,我不会提供MIPS代码,但是这里有一个算法(用C语言编写)。将其翻译成MIPS应该很简单:
int bits(unsigned int number)
{
// clear the accumulator
int accumulator = 0;
// loop until our number is reduced to 0
while (number != 0)
{
// add the LSB (rightmost bit) to our accumulator
accumulator += number & 1;
// shift the number one bit to the right so that a new
// bit is in the LSB slot
number >>= 1;
}
return accumulator;
}
找出答案的最简单方法是询问编译器。有几个在线编译器可供选择; 目前最好的是godbolt(又名Compiler Explorer)。例如,在https://godbolt.org/z/4ahfovr7z,您可以看到一个简单的比特计数算法的结果:
int pop_count(uint32_t in) {
int count = 0;
while (in) in &= in - 1, count += 1;
return count;
}
将其转换为MIPS汇编、x86-64汇编以及更近期的x86-64汇编。(我之所以提到后者,只是因为这个计算只需要一条指令。遗憾的是,即使使用-march=mips64r6
,也没有快速的MIPS popcount,但有一个快速的前导零计数)
Chris提供的链接提供了一些好的位计数方法。我建议使用这种方法,因为它既非常快速,又不需要循环,只需要位运算,这在汇编中更容易实现。
另一种获取汇编代码的方法是将代码用C语言编写,编译后查看输出的汇编代码(大多数编译器都可以产生汇编文件输出(例如gcc的-S选项),但请确保通过-O0禁用优化以获得更易于理解的代码),或者允许您查看二进制文件的反汇编)。这应该会指引你朝着正确的方向前进。
作为一个轶事,我曾经在PowerPC上进行过一些测试,以找到计算32位整数中最快的方法。我链接的方法远比其他所有方法都要好,直到我做了一个字节大小的查找表并对其进行了4次寻址。似乎ALU比引用缓存慢(通过算法运行约一百万个数字)。
使用基本的32位汇编循环很容易,我猜这是一种天真的方式,假设您有print_eax函数:
开始:
mov ebx, 97d
mov ecx, 32d
xor eax, eax
累加:
ror ebx,1
jnc 继续
inc eax
继续:
loop 累加
call print_eax