大十进制整数中的位数-Java 学习之路

给定一个大十进制整数，我如何计算bit-length，即其二进制表示的位数？

Example: bitlength("590295810358705712624") == 70

算术表达式为： bitlength = ⌊log₂(n)⌋ + 1

对于小整数，此表达式可以转换为标准库调用 . 但是具有任意数字位数的大整数呢？

我们可以从一个或两个前导数字计算 log₂ 的非常接近的估计：

log₂(8192) ≥ log₂(8100) = log₂(81) + log₂(10) * 2 = 12.98...

将其插入上面的算术表达式中，我们得到了比特长度的非常好的下界 . 但在某些情况下，为了获得准确的结果，我们必须检查更多数字，可能是最不重要的数字：

bitlength("1125899906842623") == 50
bitlength("1125899906842624") == 51

有关如何在所有情况下准确有效地计算位长的任何建议？

3 回答

计算近似对数的下限和上限并在两者相等时接受结果，我们可以在一步中完成超过90％的所有情况的计算 . 在所有其他情况下，我们将输入除以2并递归重复 .

给定n位数的输入并假设除以2在O（n）中，运行时复杂度如下：

O（1）在最好的情况下
平均
O（n）
在最坏的情况下
O（n²）

我仍然认为可以改善平均和最差情况运行时复杂性 .

以下是所述算法的示例性实现：

// Divide n by 2:
function half(n) {
  let shrink = n[0] > 1 ? 0 : 1;
  let result = new Array(n.length - shrink);
  let carry = 0.5 * shrink;
  for (let i = 0; i < result.length; ++i) {
    let d = n[i + shrink] * 0.5 + carry * 10;
    carry = d % 1;
    result[i] = Math.floor(d);
  }
  return result;
}

// Compute bit-length of n:
function bitlength(n) {
  if (n.length < 2) return Math.floor(Math.log2(n[0]            )) + 1;
  if (n.length < 3) return Math.floor(Math.log2(n[0] * 10 + n[1])) + 1;

  let lower = Math.floor(Math.log2(n[0] * 10 + n[1]    ) + Math.log2(10) * (n.length - 2));
  let upper = Math.floor(Math.log2(n[0] * 10 + n[1] + 1) + Math.log2(10) * (n.length - 2));
  if (lower === upper) return lower + 1;

  return bitlength(half(n)) + 1;
}

// Example:
console.log(bitlength([5,9,0,2,9,5,8,1,0,3,5,8,7,0,5,7,1,2,6,2,4]));

可以优化以上实现，例如，使用查找表 . 但是，为了提高运行时间的复杂性，我们需要提出一个更好的解决方案来将n除以2.随意发表评论 .

回复于 2024-06-02T16:24:13+08:00

2

我曾经写过如何将一个以字符串形式给出的任意大小的数字转换为十六进制数字字符串的答案：https://stackoverflow.com/a/2653006/64121

您可以非常轻松地将其调整为二进制字符串并获取其长度（或直接计算长度） . 更懒惰的方法是保持十六进制版本并计算所有数字，但第一个数字为四个二进制数字，最后检查第一个数字的确切位长 .

回复于 2024-06-02T16:24:13+08:00
0
这是我在BigInteger实现中的方法：
```
result = (number_of_limbs - 1) * 32 + Integer.bitlength(top_limb);
```
你应该知道四肢的数量 . 在我的例子中，它们是32位无符号整数 . 只需要处理上肢的位，但下面的简单算法将为您做到这一点：
```
if (n > 65535)
{
    result += 16;
    n >>= 16;
}
if (n > 255)
{
    result += 8;
    n >>= 8;
}
etc...
```
您必须调整负数，但这很简单：如果上肢是2的幂，则将找到的数字减1 .
回复于 2024-06-02T16:24:13+08:00

大十进制整数中的位数

3 回答

相关问题