计算已设置位的位数

Question

我想要统计一个二进制数字中被设置的位数。例如，用户输入数字97，它在二进制中表示为01100001。程序应该告诉我有3个位被设置了，使用MIPS ISA。

我能够在C中实现这个功能，但不知道如何使用汇编代码实现。

- csguy11

Answer 1

你所要寻找的通常被称为人口统计（popcount）。 Bit Twiddling Hacks 上有许多 C 语言实现（其中一些非常巧妙）。如果你熟悉 C 语言，每种方法都应该可以通过分解表达式合理地转换为 MIPS 汇编。

如果你的输入域很小（例如 0-255），你可以始终使用查找表，并将输入用作偏移量直接获取 popcount。

- Chris Schmich

Answer 2

由于这听起来像是一道作业题，我不会提供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;
}

- Gabe

Answer 3

找出答案的最简单方法是询问编译器。有几个在线编译器可供选择; 目前最好的是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，但有一个快速的前导零计数)

- jorgbrown

Answer 4

Chris提供的链接提供了一些好的位计数方法。我建议使用这种方法，因为它既非常快速，又不需要循环，只需要位运算，这在汇编中更容易实现。

另一种获取汇编代码的方法是将代码用C语言编写，编译后查看输出的汇编代码（大多数编译器都可以产生汇编文件输出（例如gcc的-S选项），但请确保通过-O0禁用优化以获得更易于理解的代码），或者允许您查看二进制文件的反汇编）。这应该会指引你朝着正确的方向前进。

作为一个轶事，我曾经在PowerPC上进行过一些测试，以找到计算32位整数中最快的方法。我链接的方法远比其他所有方法都要好，直到我做了一个字节大小的查找表并对其进行了4次寻址。似乎ALU比引用缓存慢（通过算法运行约一百万个数字）。

- Eli Iser

Answer 5

使用基本的32位汇编循环很容易，我猜这是一种天真的方式，假设您有print_eax函数：

开始：

mov ebx, 97d

mov ecx, 32d

xor eax, eax

累加：

ror ebx,1

jnc 继续

inc eax

继续：

loop 累加

call print_eax

- Javier Munoz

---

问题被标记为 #mips。 - ecm

目前来说，你的回答不太清楚。请编辑并添加更多细节，以便帮助他人理解这是如何回答所提出的问题的。您可以在帮助中心找到有关撰写良好答案的更多信息。 - Community