在JavaScript中将整数转换为任意排序的字节数组的最快方法？ [英] Fastest way to convert a integer to arbitrarily ordered byte arrays in JavaScript?

问题描述

我想转换 MIN_SAFE_INTEGER 到 MAX_SAFE_INTEGER 范围的JavaScript编号（不包括53位）符号）成为一个超过7个字节的比特串，移位两个以允许符号和空标识符。

I'm looking to convert the MIN_SAFE_INTEGER through MAX_SAFE_INTEGER range of a JavaScript number (53-bits not including the sign) into a string of bits spread over 7 bytes shifted two to allow for sign and null identifiers.

到目前为止，我提出的最好的是：

Thus far the best I've come up with is:

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);
}

小提琴

正如您所知，这将是可悲的缓慢（并且这些位仍然没有被转移所有7个活动字节中的两个位置。）

As you can tell right off, this would be abominably slow (and the bits still haven't been shifted two places across all 7 active bytes.)

有没有办法更快地完成此操作？理想情况下，完全避免字符串解析？

Is there any way to do this faster? Ideally by avoiding the string parsing altogether?

推荐答案

javascript中的按位运算只有32位宽。但是，移位相当于乘法或除以2的幂，并且这些以完全浮点精度发生。

Bitwise ops in javascript are only 32 bits wide. But shifting is equivalent to multiplication or division by a power of two, and these happen with full floating-point precision.

所以你想要做的就是直截了当。移位以获得低阶位中的有趣部分，并屏蔽其余部分。
例如你有一个很大的数字0x123456789abc（20015998343868）。

So what you want to do is straightforward. Shift to get the interesting part in the low-order bits, and mask off the rest. E.g. you have a big number 0x123456789abc (20015998343868).

0x123456789abc / 0x1 = 0x123456789abc。按位与0xff给出0xbc。

0x123456789abc / 0x1 = 0x123456789abc. Bitwise AND with 0xff gives 0xbc.

0x123456789abc / 0x100 = 0x123456789a.bc。按位与0xff给出0x9a。

0x123456789abc / 0x100 = 0x123456789a.bc. Bitwise AND with 0xff gives 0x9a.

0x123456789abc / 0x10000 = 0x12345678.9abc。按位与0xff给出0x78。

0x123456789abc / 0x10000 = 0x12345678.9abc. Bitwise AND with 0xff gives 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更容易生活：使用0xff屏蔽隐含为Uint8Arrays只能存储0到255之间的整数。但为了清楚起见，我将其保留，因此结果与不同的数组类型相同。

With a Uint8Array life is even easier: the masking with 0xff is implicit as Uint8Arrays can only store integers between 0 and 255. But I've left it in for clarity, and so that the result will the same with different array types.

此代码生成一个小端数组，例如
toUint8Array（0x123456789abc）返回
[0xbc，0x9a，0x78,0x56,0x34,0x12,0] 。
如果你想要big-endian，即相反顺序的字节，用 arr [6-i]替换 arr [i] 。

This code produces a little-endian array, e.g. toUint8Array(0x123456789abc) returns [0xbc,0x9a,0x78,0x56,0x34,0x12,0]. If you want big-endian, i.e. the bytes in the opposite order, replace arr[i] with arr[6-i].

（如果您希望每个数组条目中的位的顺序相反，则稍微复杂一些。将（d / j）& 0xff 替换为 bitrev（（d / j）& 0xff），其中bitrev看起来像这样：

(If you want the bits in each array entry in the opposite order this is slightly more complicated. Replace (d / j) & 0xff with bitrev((d / j) & 0xff), where bitrev looks something like this:

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< 0？ -d：d （或 Math.abs（d））是 d 。所以 arr = toUint8Array（（d <0）？1-d * 4：d * 4）返回d左移两位，符号位在最低位位（LSB）。

Finally, this only works on positive integers. But your shifting-by-two idea is easily implemented. d*4 is d shifted left by two bits. And d < 0 ? -d : d (or Math.abs(d)) is the absolute value of d. So arr = toUint8Array((d<0) ? 1-d*4 : d*4) returns d shifted left by two bits, with the sign bit in the least significant bit (LSB).

您可以使用 isFinite（）检查非数字，但是您必须小心只在数字上调用它，因为 isFinite（null），比如说实际上是 true ，因为隐式转换规则（这在ES6中已修复）：

And you can check for not-numbers with isFinite(), but you have to be careful to call it only on numbers, as isFinite(null), say, is actually true due to implicit casting rules (this is fixed in 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);
}

这篇关于在JavaScript中将整数转换为任意排序的字节数组的最快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！