count_ones 在 Rust 中是如何实现的？

Question

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

/*
* 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
}

我找到了这个 on the rust repo, but I can't make sense of it (still new to Rust!) (reproduced below).

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

Answer 1

让我们按照代码一步一步进行操作。

首先，查看您发布的代码片段 - 它包含几个宏变量（前面带有美元符号的标识符），因此假设该代码实际上是宏定义的一部分。向上滚动，我们得到以下内容：

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
        }
    }
}

现在，要查看这里的变量值，我们应该找到调用该宏的位置。一般来说，由于宏作用域规则，这可能很难，但在这里我们将只搜索同一个文件，如下所示：

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 }
}

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

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

std现在让我们在文档中查找我们感兴趣的函数。搜索count_ones汇集了一堆函数，对于每个原始数字类型都是独立的；我们将看一下的实现u8。单击src该函数上的链接即可看到代码：

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特征的一部分实现的，而不是直接在原始类型上实现。如果您检查版本 1.44.1的实现（这是撰写本文时的当前版本），您将看到我在上面从文档中引用的相同代码。