5

我想计算设置的二进制数中的位数。例如，用户输入数字 97，即二进制 01100001。该程序应该告诉我使用 MIPS ISA 设置了 3 位。

我能够在 C 中实现这一点，但我不知道如何使用汇编代码来实现它。

4

5 回答 5

6

您要查找的内容通常称为人口计数 (popcount)。

Bit Twiddling Hacks上有许多 C 实现（其中一些非常聪明）。如果您熟悉 C，则每种方法都应该在分解表达式后合理地转换为 MIPS 程序集。

如果您的输入域很小（例如 0-255），您总是可以做一个查找表并使用输入作为偏移量来直接获取 popcount。

于 2010-09-22T04:13:08.313 回答
3

由于这听起来像家庭作业，我不打算给出 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;
}
于 2010-09-22T04:22:01.287 回答
1

Chris 给出的链接提供了一些很好的位计数方法。我建议使用这种方法，因为它既非常快又不需要循环，只需要按位操作，这在汇编中更容易完成。

Another way you might get the assembly code is to make the code in C, compile it and then look at the output assembly (most compiles can produce an assembly file output (-S for gcc, but make sure to disable optimization via -O0 to get easier to understand code), or allow you to view the binary file disassembled). It should point you in the right direction.

As an anecdote, I've done some testing a while back on PowerPC (not MIPS, I know...) for the quickest way to count bits in a 32 bit int. The method I linked was the best by far from all other methods, until I did a byte sized lookup table and addressed it 4 times. It would seem that the ALU is slower than referencing the cache (running around a million numbers through the algorithm).

于 2010-09-22T07:32:53.293 回答
1

The easiest way to find out is to ask a compiler. There are several online compilers; the best one currently is godbolt (aka Compiler Explorer). For example, at https://godbolt.org/z/4ahfovr7z you can see the results of taking a simple bitcounting algorithm:

int pop_count(uint32_t in) {
  int count = 0;
  while (in) in &= in - 1, count += 1;
  return count;
}

and converting it to MIPS assembly, x86-64 assembly, and more recent x86-64 assembly. (I mention the latter only because this calculation is just a single instruction. Sadly, even with -march=mips64r6 there is no fast MIPS popcount, though there is a fast count of leading zeroes)

于 2022-01-26T20:48:33.540 回答
-2

easy with loop in basic 32bit asm, guess this is the naive way, assuming you have print_eax fun:

start:

mov ebx, 97d

mov ecx, 32d

xor eax, eax

accumulate:

ror ebx,1

jnc continue

inc eax

continue:

loop accumulate

call print_eax

于 2022-01-26T13:58:54.010 回答