计算寄存器中设置为 0 的位数

问题描述 投票:0回答:2

查看寄存器的内容并计算设置为 0 的位数,然后将该计数保存在不同的寄存器中的最有效方法是什么?

显然,循环与 LSR 一起是必要的,但我不确定如何与 AND 指令以及 EOR 一起实现它。

assembly arm
2个回答
0
投票

这里没有真正的答案。一些处理器具有给出设置位数的指令(对于通用编程来说这是一条非常无用的指令,但对于错误检测很有用)。假设您没有这样的指令,通常零绝对是寄存器最有可能保存的值,您应该专门测试它。然后你必须求助于数位。基本算法是与 1 进行“与”,将结果添加到累加器,右移,与 1 进行“与”,然后重复,直到获得所有位。或者,因为您想要零位,所以与 1 进行异或。但我们可以加快速度。您可以使用 8 位进行查找。但这会比打卡 8 更快还是更慢呢?它仅取决于特定的指令集、内存缓存等。如果我们有一个“寄存器文件”,通过索引号来标识寄存器,我们可以将寄存器 0 设置为 4,将寄存器 1 设置为 3,将寄存器 2 设置为 3,将寄存器 3 设置为 2,依此类推(16 个寄存器的计数为0 位),输出 4 位,然后使用结果来索引寄存器文件。您需要做几件事来证明开销的合理性。

另一个问题是循环或展开是否会更快。这又是高度依赖于架构的。

另一个可能的技巧是,如果设置了 MSB,则该数字为负数。负数测试比 AND 更快吗?很有可能。另一个是,乘以二或加到自身可能会设置进位标志,并且带有进位的加零可能比加寄存器更快。

有很多可能的小策略。


0
投票

考虑到所涉及的所有不同的硬件位,如果您的编译器与 GCC 兼容,我会非常仔细地查看 __builtin_popcount() 和朋友。对于普通程序员来说,这是最明智的答案,因为编译器正在为您进行指令选择。

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

至于算法,Hackers Delight 中介绍了标量的位黑客,以及查找表驱动的方法,包括使用 SIMD 混洗单元对向量执行半字节 LUT 的方法。一些矢量和标量 ISA 还包括(可选?)popcnt 指令。

0 计数显然是 8*sizeof(type) - 1s 计数,这就是 popcount 提供的。

© www.soinside.com 2019 - 2024. All rights reserved.