如何获取BigInt的位数？

Question

这里或这里没有bitLength()记录方法...如何检查本机 BigInt 值的位数？

我正在寻找一种“直接的方式”，通过一些内部信息......或者任何比转换更快的东西x.toString(2)。

---

笔记

• 并不理想，但中间的解决方法（似乎比 更快toString()）是使用基于log2(x) ... 的数学公式，适用于 BigInt。

• 这个lib 开发了一个具体的integerLogarithm(value, base)计算log2...并实现了一个bitLength()方法（没有Math.floor()嗡嗡声...），但是有很多依赖项，它是一头大象...

Answer 1

注意：以下测量是在 V8 (Chromium) 中进行的，应扩展到其他引擎以确认并发布基准测试链接。

注 2：所有这些函数都假设参数为非负数，否则可能会崩溃/循环/返回无效结果。

简单版

return x.toString(2).length

正如评论中所指出的，即使使用 toString() 感觉很麻烦，也不可能有一种渐近更快的方法（因为格式化基数为 2 的字符串是高效的并且是本机发生的）。它是 O(n) 与 bigint 的位数。除此之外，它简短易读，因此非常适合大多数用途。

更好的版本

const i = (x.toString(16).length - 1) * 4
return i + 32 - Math.clz32(Number(x >> BigInt(i)))

这仍然使用 toString() 方法，但它使用基数 16 而不是基数 2，这意味着生成的临时字符串短了 4 倍。格式化基数 16 也很高效，不需要真正的基数更改，因此仍然是 O(n)。

对于小型 bigint（32 位 +10%），使用此方法的收益是微不足道的，但对于大型 bigint（例如消息或加密系数，即 512 / 1024 / 2048 / 4096），它的速度快 2.5 到 4 倍，并且压力更小GC 因为它只分配一个 2x 长的字符串。它非常适合热代码和非小整数。

“你可能想太多了”版本

幸运的是，有一种更高效的方法，不涉及 toString() ，而是依赖于预先分配的不同大小的整数，这些整数连续与目标进行比较，以 ceil(log2(n)) 步骤获取其大小的上限。

一旦建立了上限，精确的大小就由二分法确定：

// find upper bound
let k = 0
while (true) {
    if (testersN === k) {
        testersCoeff.push(32 << testersN)
        testersBigCoeff.push(BigInt(testersCoeff[testersN]))
        testers.push(1n << testersBigCoeff[testersN])
        testersN++
    }
    if (x < testers[k]) break
    k++
}

if (!k)
    return 32 - Math.clz32(Number(x))

// determine length by bisection
k--
let i = testersCoeff[k]
let a = x >> testersBigCoeff[k]
while (k--) {
    let b = a >> testersBigCoeff[k]
    if (b)
        (i += testersCoeff[k], a = b)
}

return i + 32 - Math.clz32(Number(a))

此代码使用以下全局变量来存储缓存状态：

const testersCoeff = []
const testersBigCoeff = []
const testers = []
let testersN = 0

在我的测试中，与之前的版本相比，512 位速度快了 2 倍，4096 位速度快了 7 倍。它最多分配目标整数大小的 1 倍，尽管是多个整数。

理想版本

如果有适当的本机支持，这本质上是一个 O(1) 操作（因为引擎需要知道用于存储 bigint 的缓冲区的长度）。

就目前而言，我们可以期望的最好的事情是 O(n)，因为没有办法探测 bigint 的大小（即询问大小是否小于或大于某个 n），而这不涉及与n 在最坏的情况下。

Answer 2

这是一种 hacky（但简单）的方法，将其转换为字符串：

num.toString(2).length;

num.toString(2).length;