algorithm - 大十进制整数中的位数

Question

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

示例: 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

关于如何在所有情况下准确有效地计算位长有什么建议吗？

Answer 1

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

给定一个 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。欢迎发表评论。