rust - count_ones 在 Rust 中是如何实现的？

Question

我试着寻找 Rust 如何实现 count_ones()。我很好奇，因为它似乎大大优于我自己的天真实现(不是开玩笑)，我真的很想看看为什么它如此高效。我的猜测是 Rust 正在使用一些 asm 来完成这项工作。为了完整起见，这是我的尝试:

/*
* my attempt to implement count_ones for i32 types
* but this is much slower than the default
* implementation.
*/
fn count_ones(num: i32) -> u32 {
    let mut ans: u32 = 0;
    let mut _num = num;

    while _num > 0 {
        if _num & 0x1 == 0x1 {
            ans += 1;
        }
        _num >>= 1;
    }

    ans
}

我找到了 this在 Rust repo 协议(protocol)上，但我无法理解它(对 Rust 来说还是新手!)(转载如下)。

#[inline]
fn count_ones(self) -> u32 {
    unsafe { $ctpop(self as $ActualT) as u32 }
}

Answer 1

让我们按照代码一步步来。

首先，查看您发布的代码片段 - 它包含几个宏变量(前缀为美元符号的标识符)，因此假设这段代码实际上是macro definition .向上滚动，我们得到 the following :

macro_rules! uint_impl {
    ($T:ty = $ActualT:ty, $BITS:expr,
     $ctpop:path,
     $ctlz:path,
     $cttz:path,
     $bswap:path,
     $add_with_overflow:path,
     $sub_with_overflow:path,
     $mul_with_overflow:path) => {
        #[stable(feature = "rust1", since = "1.0.0")]
        #[allow(deprecated)]
        impl Int for $T {
             // skipped
        }
    }
}

现在，要查看此处的变量值，我们应该找到调用此宏的位置。通常，由于宏观范围规则，这可能很难，但在这里我们将只搜索相同的文件，并且 here it is :

uint_impl! { u8 = u8, 8,
    intrinsics::ctpop8,
    intrinsics::ctlz8,
    intrinsics::cttz8,
    bswap8,
    intrinsics::u8_add_with_overflow,
    intrinsics::u8_sub_with_overflow,
    intrinsics::u8_mul_with_overflow }

(以及多个其他调用)。将此与宏定义进行比较，我们看到我们正在寻找的函数将扩展为以下内容:

#[inline]
fn count_ones(self) -> u32 {
    unsafe { intrinsics::ctpop8(self as u8) as u32 }
}

最后，正如 Stargateur 在评论中提到的，intrinsics::ctpop8 是一个 LLVM 内在函数，即此调用直接转换为 LLVM 指令。

---

但是，有一个更好的方法来找出什么是什么。

现在让我们在 std documentation 中寻找我们感兴趣的函数.搜索 count_ones 汇集了一堆函数，分别针对每种原始数字类型；我们来看看 implementation for u8 .单击函数上的 src 链接会为我们带来 to the code:

doc_comment! {
    concat!("Returns the number of ones in the binary representation of `self`.

# Examples

Basic usage:

```
", $Feature, "let n = 0b01001100", stringify!($SelfT), ";

assert_eq!(n.count_ones(), 3);", $EndFeature, "
```"),
    #[stable(feature = "rust1", since = "1.0.0")]
    #[rustc_const_stable(feature = "const_math", since = "1.32.0")]
    #[inline]
    pub const fn count_ones(self) -> u32 {
        intrinsics::ctpop(self as $ActualT) as u32
    }
}

...它只是直接调用了我们之前发现的 intrinsics::ctpop 函数。

---

现在您可能想知道，为什么这两次搜索会产生不同的代码片段。原因很简单:您所指的提交来自相当旧的 rustc 版本——如果我没理解错的话，它是 pre-1.0；那时，数值运算是作为 Num 特性的一部分实现的，而不是直接在原始类型上实现。如果您查看 version 1.44.1 的实现，这是撰写本文时的最新版本，您会看到我在上面从文档中引用的相同代码。