3

我在 Rust 中有以下 Hamming 权重代码，它为0xffffand返回垃圾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()——编译器在我编写这段代码时告诉我，这非常棒，但我选择不使用它。

4

1 回答 1

12

我不得不用它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
}
于 2017-04-25T13:52:37.533 回答