我认为没有什么比最大化的天真方法更好了。一个尝试是使用这个等式
x + y = min(x, y) + max(x, y)
因此
max(ctz(x), ctz(y)) = ctz(x) + ctz(y) - min(ctz(x), ctz(y))
通过这种方式，我们可以将最大函数简化为已经优化过的最小函数，尽管需要进行一些额外的操作。
以下是不同方法的Rust实现示例：
pub fn naive(x: u64, y: u64) -> u32 {
x.trailing_zeros().max(y.trailing_zeros())
}
pub fn sum_minus_min(x: u64, y: u64) -> u32 {
x.trailing_zeros() + y.trailing_zeros() - (x | y).trailing_zeros()
}
pub fn nielsen(x: u64, y: u64) -> u32 {
let x_lsb = x & x.wrapping_neg();
let y_lsb = y & y.wrapping_neg();
let xy_lsb = x_lsb | y_lsb;
let lsb = xy_lsb & xy_lsb.wrapping_neg();
let xy_max_lsb = if xy_lsb == lsb { lsb } else { xy_lsb ^ lsb };
xy_max_lsb.trailing_zeros()
}
pub fn timmermans(x: u64, y: u64) -> u32 {
let loxs = !x & x.wrapping_sub(1);
let loys = !y & y.wrapping_sub(1);
return (loxs | loys).count_ones();
}
pub fn kealey(x: u64, y: u64) -> u32 {
((x | x.wrapping_neg()) & (y | y.wrapping_neg())).trailing_zeros()
}
我的机器上的结果：
ctz_max/naive time: [279.09 ns 279.55 ns 280.10 ns]
ctz_max/sum_minus_min time: [738.91 ns 742.87 ns 748.61 ns]
ctz_max/nielsen time: [935.35 ns 937.63 ns 940.40 ns]
ctz_max/timmermans time: [803.39 ns 806.98 ns 810.76 ns]
ctz_max/kealey time: [295.03 ns 295.93 ns 297.03 ns]
天真的实现击败了所有其他实现。唯一能与天真实现竞争的是马丁·基利提出的方法。请注意，由于测试工具的一些开销，实际因素可能比时间指示的要高。
很明显，你只有几个CPU指令可以用来优化天真实现，所以我认为你无法做任何事情。作为参考，这里是Rust编译器在现代x86_64处理器上将这些实现编译为独立函数时生成的汇编代码。
example::naive:
tzcnt rcx, rdi
tzcnt rax, rsi
cmp ecx, eax
cmova eax, ecx
ret
example::sum_minus_min:
tzcnt rcx, rdi
tzcnt rax, rsi
add eax, ecx
or rsi, rdi
tzcnt rcx, rsi
sub eax, ecx
ret
example::nielsen:
blsi rax, rdi
blsi rcx, rsi
or rcx, rax
blsi rax, rcx
xor edx, edx
cmp rcx, rax
cmovne rdx, rcx
xor rdx, rax
tzcnt rax, rdx
ret
example::timmermans:
lea rax, [rdi - 1]
andn rax, rdi, rax
lea rcx, [rsi - 1]
andn rcx, rsi, rcx
or rcx, rax
xor eax, eax
popcnt rax, rcx
ret
example::kealey:
mov rax, rdi
neg rax
or rax, rdi
mov rcx, rsi
neg rcx
or rcx, rsi
and rcx, rax
tzcnt rax, rcx
ret
在我运行的基准测试中，函数被内联，循环部分展开，并且一些子表达式被提取出内部循环，所以汇编代码看起来比上面的要复杂得多。
为了进行测试，我使用了Criterion。以下是额外的代码：
use criterion::{black_box, criterion_group, criterion_main, Criterion};
const NUMBERS: [u64; 32] = [
...
];
fn bench<F>(func: F)
where
F: Fn(u64, u64) -> u32,
{
for x in NUMBERS {
for y in NUMBERS {
black_box(func(x, y));
}
}
}
fn compare(c: &mut Criterion) {
let mut group = c.benchmark_group("ctz_max");
group.bench_function("naive", |b| b.iter(|| bench(naive)));
group.bench_function("sum_minus_min", |b| b.iter(|| bench(sum_minus_min)));
group.bench_function("nielsen", |b| b.iter(|| bench(nielsen)));
group.bench_function("timmermans", |b| b.iter(|| bench(timmermans)));
group.bench_function("kealey", |b| b.iter(|| bench(kealey)));
}
criterion_group!(benches, compare);
criterion_main!(benches);
NUMBERS是使用这段Python代码生成的，目的是尽可能地增加min()函数的分支预测难度：
[
random.randrange(2 ** 32) * 2 ** random.randrange(32)
for dummy in range(32)
]
我正在运行基准测试使用的内容。
RUSTFLAGS='-C target-cpu=native -C opt-level=3' cargo bench
在第八代i7处理器（威士忌湖）上。
ctz(x)被实现为clz(rbit(x))。由于我们有max(clz(x), clz(y)) = clz(min(x,y))，这使得我们可以执行clz(min(rbit(x), rbit(y)))，从而节省了一个clz。（并且在这种架构上，min很容易无分支地实现。）因此，了解您的架构如何实际执行ctz可能会有所帮助。 - Nate Eldredge