rust - 计算前导/尾随 1/0 的效率有什么不同吗？

Question

我正在设计一个带前缀的可变长度整数。

Rust 有计算前导和尾随 1 和 0 的方法：https ://doc.rust-lang.org/std/primitive.u64.html#method.leading_zeros

这些方法在 x86_64、arm32 和 arm64 上的效率有什么区别吗？

例如，如果计算尾随 1 比尾随 0 快，我将使用 xxxx0111 而不是 xxxx1000 作为长度编码字节（在本例中是三个后续字节）。

Answer 1

在所有 3 个 ISA：x86*、ARM、AArch64 上，计算尾随零比尾随零快。它们都提供零计数指令，例如 x86 bsf（查找最低设置位）或 x86 BMI1 tzcnt（尾随零计数）。计算运行时变量中的前导/尾随需要否定输入。

ARM / AArch64 提供前导零计数，但尾随零的最佳选择是rbit/clz到位反转（从 ARMv6t2 或 ARMv7 开始）。https://godbolt.org/z/Yr7eac。在此之前，编译器必须用 隔离最低设置位x & -x，计算其中的前导零，然后取31-clz(x&-x).

---

（在 x86 上，使用 BMI1 计算前导零最有效。没有它，bsr可以为您提供最高设置位的位置，因此编译器需要31-bsr(x)实现 clz。在 AMD CPU 上，bsf / bsr 比它们的 tzcnt / lzcnt 对应物慢得多, 所以如果可能的话，最好用-march=nativeRust 等价物进行编译。）