深入 V8 引擎：“小整数”到底有多小？

原文：V8 Internals: How Small is a “Small Integer?”
作者：Franziska Hinkelmann
译者：justjavac(迷渡)

原文副标题：“When binary is useful outside of a coding interview”

V8 是谷歌的开源 JavaScript 引擎。Chrome，Node.js 和许多其他应用程序都使用了 V8 引擎。如果你曾经听过关于 V8 的演讲，或者读过关于 V8 的文章：Understanding V8’s Bytecode（中文：理解 V8 的字节码），你一定听说过 Smis，小整数。本文通过深入 V8 的源代码，具体研究一下 Smis 到底有多大。

根据规范，JavaScript 并不知道整数（除了最近引入的 BigInts）（中文：BigInt：JavaScript 中的任意精度整数）。它只知道 IEEE 浮点数。但是许多操作都是基于整数，比如程序中的 for 循环。所有 JavaScript 引擎都有一个特殊的整数表示方式。V8 有所谓的 Smis 小整数。

Smis 在 64 位平台上的范围是 -2³¹ 到 2³¹-1（2³¹≈2*10⁹）。如果你查看 V8 源码，这可能并不是非常明显。kSmiMinValue 并 kSmiMaxValue 在 include/v8.h 中定义如下：

static const int kSmiMinValue = 
  (static_cast<unsigned int>(-1)) << (kSmiValueSize — 1);
static const int kSmiMaxValue = -(kSmiMinValue + 1);

它是如何等于 -2³¹ 和 2³¹-1 的呢？让我们将上面的 C++ 代码分解一下。

<< 是按位左移运算。左移意味着我们将数字的二进制表示移到左边，并用零填充右边。例如，5<< 3 = 40。

您可能已经注意到了，正数的左移与乘以 2 相同。

静态转换为无符号整数

static_cast<unsigned int>(-1)

当我们将负值转换为无符号整数（即正数）时会发生什么？所有的二进制位保持不变，但值的表示却不同了。转换为无符号整数后，我们就可以把这个数作为正数来进行左移运算了。

那么 -1 的二进制表示是什么呢？在二进制补码中，-1 表示为 (111...111)_2 因为 2⁶³-2⁶²-2⁶¹- … -2²-2¹–1 = 1。

如果您查看 V8 源代码中的 definitions，您会发现在 64 位计算机上 kSmiValueSize 被定义为 32，于是：

kSmiMinValue =(static_cast<unsigned int>(-1)) << (kSmiValueSize — 1)
             = (111...111)_2 << (32-1) 
             = (111...111)_2 << 31
             = (11...1100...00)_2  // 31个零
             = -2^31

现在我们可以使用这个结果来对 kMaxValue 进行初始化。

int kSmiMaxValue = -(kSmiMinValue + 1);

显而易见，kSmiMaxValue = -(-2^31+1) = 2^31-1。在 64 位平台上 V8 对 Smis 定义的范围是 [-2³¹，2³¹-1]。

32 位平台

在 32 位平台上 kSmiValueSize = 31。所以我们把它换为 30，计算得到 kMinValue = -2^30。注意，2³⁰≈10⁹。

为什么 Smis 在 32 位平台上的范围要小一点呢？在引擎 内部，V8 使用最低有效位将所有 JavaScript 值标记为堆栈对象或者 Smis。如果最低有效位是 1，则是指针。如果是 0，则是 Smi。这意味着 32 位整数只能使用 31 位存储 Smi 值，因为一位（最低有效位）用作标记。

V8 使用最低有效位将所有值标记为 Smis 或堆指针。

其实 Smis 并没有你想象的那么小，但它们很容易以按位编码的方式来存储到 32 位或 64 位整数中。

附加题：给定一个非空的整数数组，其中某个元素只出现了一次，其余每个元素都出现了两次。找到那个唯一元素。您可以使用二进制表示方式，时间复杂度为 O(n)，空间复杂度为 O(1)，你能找到解决方案吗？

PS：很多人对文章的笔记感兴趣，小姐姐回复说，她使用的是 dotted Leuchturm1917 和 Pigma Microns。