Rust 中 Log2 的计算上限

Question

我想在 Rust 中计算以下内容：

Python 等价于：

math.ceil(math.log(b+1, 2))

ceil(log_2 n+1)

我试过：

a+1.log2() 
(a+1).log2()

但我收到错误 use of unstable library feature 'int_log'。我不想使用不稳定的库功能。计算 log2 的最简单方法是什么，如果可能的话没有任何外部板条箱？

Answer 1

Rust 对整数和浮点数的区别非常讲究。您不能只键入一个整数并期望它自动成为 auto-casted。始终在末尾添加 . 作为浮点数。

您似乎试图对整数调用该函数。试试这个：

试试这个：

(1.).log2().ceil()

或

(a as f32 + 1.).log2().ceil()

如果您希望最终结果为整数，您可以在末尾使用 as i32。如果您想要双精度浮点数，请将 f32 替换为 f64.

参考：

https://doc.rust-lang.org/std/primitive.f32.html#method.ceil

https://doc.rust-lang.org/std/primitive.f32.html#method.log2

Answer 2

如果这是 time-critical 那么您可以使用数据类型的知识来加快速度。

如果输入是一个正整数（比如说u64），那么log2(x)就是几乎最后一个非1位的索引，您可以使用 u64::leading_zeros 确定。实际上log2(x+1)就是x的最后一个非1位的索引。这给出：(playground)

pub fn main() {
    for a in 0..10u64 {
        let v = (a as f32 + 1.).log2().ceil();
        let w = u64::BITS - a.leading_zeros();
        println!("{} {} {}", a, v, w);
    }
}

产出

需要更加小心地处理 sign-bit 等带符号的数字，例如 i64。

如果您的数字是 floating-point 值，您仍然可以使用一些技巧来加快速度，特别是如果您不愿意处理 NaN、Inf 和非规范化数字。

特别是，对于 f64，“正常”数字的位模式是 52 位“分数”，11 位尾数和 1 位符号位。调用尾数的11位e浮点数的值为(sign)*(1+fraction/2^52)*2^(e-1023)

所以log2(x) = log2(1+fraction/2^52) + (e-1023).

e-1023部分为整数，其余为0<=log2(1+fraction/2^52)<1，fraction==0时为零。所以 ceil(log2(x)) = if fraction==0 {e-1023} else {e-1022}.

这给了我们 this:

pub fn main() {
    for a in -20..20i64 {
        let f = (a as f64)/4.0 + 1.0;
        let v = f.log2().ceil();
        let b: u64 = f.to_bits();
        let s = (b >> 63) & 1;
        let e = (b >> 52) & ((1<<11)-1);
        let frac = b & ((1<<52) -1);
        let z = if frac==0 { e as i64 - 1023 } else { e as i64 -1022 };
        println!("{:0.2} {:064b} : {:01b} {:011b} {:052b} {} {}", f, b, s, e, frac, z, v);
    }
}

哪个输出（修剪掉位表示后）

...
-0.75 ... -2 -2
-0.50 ... -1 -1
-0.25 ... 0 -0
 0.00 ... 0 0
 0.25 ... 1 1
 0.50 ... 1 1
 0.75 ... 1 1
 1.00 ... 1 1
 1.25 ... 2 2
 1.50 ... 2 2
 1.75 ... 2 2
 2.00 ... 2 2
...

同样，这仅在 1+a 为正常数时成立。如果需要，您需要添加条件来处理这些条件。（你应该，除非你确定你不需要）。

类似的技巧可以用于 u32 和 f32 类型。

Rust 中 Log2 的计算上限

Computing Ceil of Log2 in Rust

rust