为什么我的汉明权重函数在 C 中有效但在 Rust 中无效?
Why does my Hamming weight function work in C but not in Rust?
我在 Rust 中得到了以下汉明权重代码,returns 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()
- 当我写这段代码时编译器告诉我,这非常棒,但我选择不使用它。
I had to use u64
to prevent overflow panics on 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
}
我在 Rust 中得到了以下汉明权重代码,returns 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()
- 当我写这段代码时编译器告诉我,这非常棒,但我选择不使用它。
I had to use
u64
to prevent overflow panics on0xffff
那是你的问题。原来的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
}