JavaScript中将整数转换为任意排序的字节数组的最快方法是什么？

Question

JavaScript中将整数转换为任意排序的字节数组的最快方法是什么？

11

我想要将 JavaScript 数字的 MIN_SAFE_INTEGER 到 MAX_SAFE_INTEGER 范围（53位不包括符号）转换为一串跨越7个字节的比特流字符串，向左偏移两位以允许符号和空标识。

到目前为止，我能想到的最好方案是：

function toUint8Array(data) {
    data = data.toString(2);
    data = new Array(65 - data.length).join('0') + data;
    var ret = new Uint8Array(data.length / 8);
    for (var i = 0; i < 8; i++) {
        ret[i] = 0;
        ret[i] += (data[i * 8] == '1' ? 128 : 0);
        ret[i] += (data[(i * 8) + 1] == '1' ? 64 : 0);
        ret[i] += (data[(i * 8) + 2] == '1' ? 32 : 0);
        ret[i] += (data[(i * 8) + 3] == '1' ? 16 : 0);
        ret[i] += (data[(i * 8) + 4] == '1' ? 8 : 0);
        ret[i] += (data[(i * 8) + 5] == '1' ? 4 : 0);
        ret[i] += (data[(i * 8) + 6] == '1' ? 2 : 0);
        ret[i] += (data[(i * 8) + 7] == '1' ? 1 : 0);
    }
    return (ret);
}

Fiddle

很明显，这种方法速度非常慢（而且比特位还没有在所有7个活动字节中移动两个位置）。

有没有更快的方法？最好是完全避免字符串解析？

- CoryG

实际上，DataView如果使用得当（即不是你尝试的方式），可以提供适度的速度改进（在Firefox中为3倍，在Chrome中为1.5倍，在Internet Explorer中为7.5倍），而我可能正在进行次优化。 - Jaromanda X

@JaromandaX，我很想看看你是如何管理它以产生我试图获得的输出的。 - CoryG

我可以创建一个fiddle，但是...输入严格限制在MIN_SAFE_INTEGER -> MAX_SAFE_INTEGER之间 - 一个问题...符号/空位应该是第7个字节的LSB还是第一个字节的MSB？ - Jaromanda X

@JaromandaX 符号位是第一个字节的第一位，空位是第一个字节的第二位就像这个只到32位的 fiddle。我对 MAX_SAFE_INTEGER 允许的 53 位感到非常高兴，因为我在使用 bignumber.js，如果可以的话，我真的很想避免对第 33 到 53 位进行字符串解析。 - CoryG

2个回答

1

我研究了这个问题，和我的几个数学计算机科学方面的朋友商量后，我们的结论是按照你描述的方法是无法实现的。

我认为你只能采用字符串解析的方法。

- Michael McPherson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hexwab · Accepted Answer

在 JavaScript 中，位运算只支持 32 位宽度。但是移位等价于乘以或除以二的幂次方，并且这些操作在完整的浮点精度下进行。

因此，您想要做的很简单。通过移位将有趣的部分放在低位比特中，然后掩码掉其余部分。例如：您有一个大数 0x123456789abc（20015998343868）。

0x123456789abc / 0x1 = 0x123456789abc。与 0xff 的按位与操作得到 0xbc。

0x123456789abc / 0x100 = 0x123456789a.bc。与 0xff 的按位与操作得到 0x9a。

0x123456789abc / 0x10000 = 0x12345678.9abc。与 0xff 的按位与操作得到 0x78。

依此类推。代码如下：

function toUint8Array(d) {
    var arr = new Uint8Array(7);
    for (var i=0, j=1; i<7; i++, j *= 0x100) {
        arr[i] = (d / j) & 0xff;
    }
    return arr;
}

使用Uint8Array会更加简单：因为Uint8Array只能存储0到255之间的整数，所以掩码操作（与0xff相与）是隐含的。但是为了清晰起见，并且使得结果适用于不同类型的数组，我保留了这个操作。

这段代码生成一个小端序的数组，例如toUint8Array(0x123456789abc)返回[0xbc,0x9a,0x78,0x56,0x34,0x12,0]。如果你需要大端序（即相反顺序的字节），请将arr[i]替换为arr[6-i]。

（如果你需要每个数组元素中的位按相反顺序排列，则稍微复杂一些。将(d / j) & 0xff替换为bitrev((d / j) & 0xff)，其中bitrev类似于以下内容：）

function bitrev(byte) {
   var table = [ 0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110,
                 0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111 ];
   return table[byte >> 4] + (table[byte & 0xf] << 4);
}

最后，这仅适用于正整数。但是您的移位两位的想法很容易实现。d * 4是d左移两个比特位。而d <0？-d：d（或Math.abs（d））是d的绝对值。因此，arr = toUint8Array（（d<0）？1-d*4：d*4）返回了左移两位的d，符号位在最低有效位（LSB）。

您可以使用isFinite()检查非数字，但必须小心仅在数字上调用它，例如isFinite(null)实际上由于隐式转换规则而为true（这在ES6中已修复）：

function toUint8Array_shifted_signed(d) {
   /* bit 0 is sign bit (0 for +ve); bit 1 is "not-a-number" */
   if (typeof d !== 'number' || !isFinite(d)) {
       d = 2; 
   } else {
       d = (d<0) ? 1-d*4 : d*4;
   }

   return toUint8Array(d);
}