为什么我的汉明重量函数在C语言中可用但在Rust语言中不可用？

Question

我能翻译如下的内容，涉及到it技术。请注意，我保留了HTML标签。

我在Rust中编写了以下海明权重（Hamming weight）代码，对于0xffff和0xffffffff返回的是垃圾数据，但相同的C代码却可以正常运行。因此，我一定是对Rust位级操作的理解存在误解。该代码已经完全加上括号，因此我认为这不是一个运算符优先级问题。

C语言代码如下：

#include <stdio.h>

int hamming_weight(int val) {
    int v1 = val - ((val >> 1) & 0x55555555);
    int v2 = (v1 & 0x33333333) + ((v1 >> 2) & 0x33333333);
    return (((v2 + (v2 >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}

int main() {
    printf("%x -> %d\n", 7, hamming_weight(7));
    printf("%x -> %d\n", 0xff, hamming_weight(0xff));
    printf("%x -> %d\n", 0xffff, hamming_weight(0xffff));
    printf("%x -> %d\n", 0xffffffff, hamming_weight(0xffffffff));
    return 0;
}

结果如下：

7 -> 3
ff -> 8
ffff -> 16
ffffffff -> 32

在 Rust 中（我必须使用 u64 来防止在 0xffff 上溢出引发恐慌）：

fn hamming_weight(val: u64) -> u64 {
    let v1 = val - ((val >> 1) & 0x55555555);
    let v2 = (v1 & 0x33333333) + ((v1 >> 2) & 0x33333333);
    (((v2 + (v2 >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24
}

fn main() {
    println!("{:x} {}", 7, hamming_weight(7));
    println!("{:x} {}", 0xff, hamming_weight(0xff));
    println!("{:x} {}", 0xffff, hamming_weight(0xffff));
    println!("{:x} {}", 0xffffffffu32, hamming_weight(0xffffffffu64));
}

结果如下：

7 3
ff 8
ffff 2064
ffffffff 135272480

我正在使用 Rust 1.16 版本。我知道 Rust 有一个名为 count_ones() 的函数 - 当我编写这段代码时编译器告诉了我，这非常神奇，但我选择不使用它。

- Mark Wright

---

它是在你写这段代码的时候告诉你的？ - Veedrac

用fn hamming_weight(val: u64) -> u32替换声明。我收到了这个错误信息：help: here are some functions which might fulfill your needs: ... - .count_ones()。Rust编译器的错误信息非常棒。 - Mark Wright

Answer 1

我不得不使用u64来防止在0xffff上溢出导致崩溃。

那就是你的问题了。原始的C代码依赖于操作的溢出。增加类型的大小并不能解决它，但允许溢出包裹起来却可以：

fn hamming_weight(val: u32) -> u32 {
    let v1 = val - ((val >> 1) & 0x55555555);
    let v2 = (v1 & 0x33333333) + ((v1 >> 2) & 0x33333333);
    (((v2 + (v2 >> 4)) & 0xF0F0F0F).wrapping_mul(0x1010101)) >> 24
}

- Shepmaster

---

谢谢 - 那真是令人困惑。 - Mark Wright