在Rust中，count_ones是如何实现的？

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
}

我在rust代码库中发现了 这个 ，但我无法理解它（对Rust还很陌生！）（如下所示）。

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

- Kiwi breeder

---

https://releases.llvm.org/3.2/docs/LangRef.html#int_ctpop - Stargateur

@Cerberus的回答展示了Rust如何使用专门的asm来实现这一点。除了这样的asm之外，我所知道的最快的纯软件实现是这个。 - Jmb

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

最后，正如Stargateur在评论中提到的那样，intrinsics::ctpop8是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 版本——如果我理解正确，是1.0之前的版本；那时，数值运算是作为 Num trait 的一部分实现的，而不是直接在原始类型上实现。如果你查看 版本1.44.1 的实现，这是我从文档中引用的相同代码。

- Cerberus