字节数组转换为Uint64字符串

7
让我们考虑以下情况。Go例程创建一个字节数组,将一个Uint64数字5577006791947779410以8个字节的大端形式打包为[77, 101, 130, 33, 7, 252, 253, 82]。在JavaScript代码中,我将这些字节作为Uint8Array接收。我们知道JavaScript目前不支持Uint64作为安全数值类型,并且不能对大于32位的整数执行位运算,因此像buf [0] << 56这样的操作永远不起作用。那么,将这些字节直接解码为数值字符串“5577006791947779410”的过程是什么?

P.S. 我知道在 JavaScript 中有很多 处理大整数的 , 但通常它们都非常庞大并提供大量的数学运算,而我在这里不需要。我正在寻找一个简单的、现代的、直接的解决方案,只需要将 BE-packed 的 Uint64Int64 字节解码为数字字符串。你有什么想法吗?

4个回答

9

编辑:对于转换(U)int64,我现在一定会推荐@LS_DEV的解决方案。只有当有未知或更大数量的字节时,才会使用我的解决方案。

我从https://dev59.com/RGMl5IYBdhLWcg3wK0WA#21668344开始,并进行了修改:

function Int64ToString(bytes, isSigned) {
  const isNegative = isSigned && bytes.length > 0 && bytes[0] >= 0x80;
  const digits = [];
  bytes.forEach((byte, j) => {
    if(isNegative)
      byte = 0x100 - (j == bytes.length - 1 ? 0 : 1) - byte;
    for(let i = 0; byte > 0 || i < digits.length; i++) {
      byte += (digits[i] || 0) * 0x100;
      digits[i] = byte % 10;
      byte = (byte - digits[i]) / 10;
    }
  });
  return (isNegative ? '-' : '') + digits.reverse().join('');
}

const tests = [
  {
    inp: [77, 101, 130, 33, 7, 252, 253, 82],
    signed: false,
    expectation: '5577006791947779410'
  },
  {
    inp: [255, 255, 255, 255, 255, 255, 255, 255],
    signed: true,
    expectation: '-1'
  },
];

tests.forEach(test => {
  const result = Int64ToString(test.inp, test.signed);
  console.log(`${result} ${result !== test.expectation ? '!' : ''}=== ${test.expectation}`);
});

起初,标记会通过检查最高位是否被设置(bytes [0] > 128)来计算。对于负数,比特必须被否定(255-byte),并且必须将1添加到数字中(因此为256而不是255,用于最后一个字节)。
forEach循环的基本思想是将每个字节拆分为其十进制数字(byte%10),并计算开销(字节-数字[i])/ 10 Math.floor(byte / 10)下一个数字。对于下一个字节,必须添加上一个字节数字的移位结果(byte + = digits [i] * 256digits [i] << 8 )。
该代码经过优化,以使其简短、简单和灵活。如果您使用字符串而不是字节或数字,并且不想使用任何库,则似乎转换性能并不重要。否则,函数可以针对性能进行优化:最多可以同时处理四个字节,只需替换 0x100 0x80 ,另外(在情况下仅剩两个字节组的(U)Int64的情况下) forEach 循环可以展开。分组十进制数字可能不会增加性能,因为结果字符串必须用零填充,从而引入了在最终结果中删除前导零的需要。

谢谢您的回复!这似乎对uint64很有效。为了使其与int64一起使用,我需要做哪些修改?我在这里创建了一个游乐场:https://jsfiddle.net/wcqLj1qg/。 - VisioN
1
我已经更新了我的答案并上传到https://codepen.io/stephtr/pen/brBvxr。 必要的修改是(显然)添加减号,否定位并减去1。 - Stephan
可以通过将“byte> 0”更改为“byte”,因为“byte”始终是正数,使其略微紧凑。同样,“j == bytes.length - 1?0:1”可以简单地写为“j!= bytes.length - 1”,因为布尔值将被强制转换为数字 :) - csander
我在编写代码时考虑过这个问题,但我认为那会降低可读性。 - Stephan

4
另一种方法:将问题分为两个uint32,以保持计算的可管理性。
考虑较低和较高的uint32(l和h)。完整的数字可以写成h*0x100000000+l。考虑十进制,也可以考虑较低的9位数字和剩余的较高数字(ld和hd):ld=(h*0x100000000+l)%1000000000hd=(h*0x100000000+l)/1000000000。通过一些算术和代数运算符的属性,可以将这些操作分解为安全的“半”64位操作,并在最后组合字符串。

function int64_to_str(a, signed) {
  const negative = signed && a[0] >= 128;
  const H = 0x100000000, D = 1000000000;
  let h = a[3] + a[2] * 0x100 + a[1] * 0x10000 + a[0]*0x1000000;
  let l = a[7] + a[6] * 0x100 + a[5] * 0x10000 + a[4]*0x1000000;
  if(negative) {
     h = H - 1 - h;
     l = H - l;
  }
  const hd = Math.floor(h * H / D + l / D);
  const ld = (((h % D) * (H % D)) % D + l) % D;
  const ldStr = ld + '';
  return (negative ? '-' : '') +
         (hd != 0 ? hd + '0'.repeat(9 - ldStr.length) : '') + ldStr;
}

let result = int64_to_str([77, 101, 130, 33, 7, 252, 253, 82], false);
let expectation = '5577006791947779410';
console.log(result + ' ' + (result === expectation ? '===' : '!==') + ' ' + expectation);

result = int64_to_str([255, 255, 255, 255, 255, 255, 255, 255], true);
expectation = '-1';
console.log(result + ' ' + (result === expectation ? '===' : '!==') + ' ' + expectation);

如评论中所述,该算法即使 (h % D) * (H % D) 的值比 Number.MAX_SAFE_INTEGER 更大,也可以正常工作,因为丢失的位数仍然是零。

1
尽管这对处理固定大小的整数是更好的方法,但在某些情况下它不会正确地工作。我认为应该放弃Math.trunc(ld/D)部分,因为第一个总和在数学上已经包含了该部分。纠正后,我仍然不确定它是否能够正确地工作。h*H可以得到远高于Number.MAX_SAFE_INTEGER的数字。通过除以D并截断来消除精度损失。然而,我更担心的是(h%D)*(H%D),因为 D*(H%D)也太大了,这次需要全部精度。 - Stephan
更具体地说,D 的最后11位(因此为0x800),因此 H%D 已经为零,因此由于“精度损失”而隐式设置它们为零不会引入任何错误。 另外一点需要注意的是:当 hd 为零时,不应附加前导零。 - Stephan
@Stephan 做得好。如果你愿意,欢迎将其发布为答案。你比我花了更多的精力 :-) - LS_ᴅᴇᴠ
我更新了您的答案,但编辑似乎被拒绝了。随意复制它;) - Stephan
谢谢您的回复!我希望我能给你们更多的赞 ;) - VisioN
显示剩余3条评论

1
这是 UInt64 版本 - 我无法想象交换会那么困难:

<!DOCTYPE html>
<html>

<body>
<span id='out1'></span>
<br>
<span id='out2'></span>
<br>
<span id='out3'></span>
</body>

<script>
fnl='';
be=[77, 101, 130, 33, 7, 252, 253, 82];

function paddedBinary(n) {
pad='';
sv=128;
while (sv>n) {pad+='0';sv/=2;}
return pad+n.toString(2);
}

for (let i=0;i<8;i++)
fnl+=paddedBinary(be[i]);

out1.textContent=fnl;

dec=new Array(64);
for (let i=0;i<64;i++) dec[i]=new Array(21).fill(0);

function make2s() {
dec[0][0]=1;
for (let i=1;i<64;i++) {
for (let j=0;j<21;j++) 
dec[i][j]=2*dec[i-1][j];
for (let j=0;j<21;j++) 
if (dec[i][j]>9) {
dec[i][j]-=10;
dec[i][j+1]++;
}
}
}

function int64add(v1,v2) {
var res=new Array(21).fill(0);
for (let i=0;i<21;i++)
res[i]=v1[i]+v2[i];
for (let i=0;i<21;i++)
if (res[i]>9) {
res[i]-=10;
res[i+1]++;
}
return res;
}

make2s();
for (let i=0;i<64;i++)
out2.textContent+=dec[i]+' :: ';

cv=new Array(21).fill(0);
for (let i=0;i<fnl.length;i++)
if (fnl[i]=='1') cv=int64add(cv,dec[63-i]);

out3.textContent=cv;

</script>
</html>

paddedBinary()函数返回一个完整的8位二进制数,因此我们可以将'fnl'创建为BigEndian的64位字符串。
由于JavaScript无法进行完整的64位算术运算,因此我创建了dec[]数组,以将每个2的幂作为单独的数字存储,通过加倍每个先前的数字并平滑十位数来实现。
然后只需添加我们想要的位,这使用类似于平滑十位数的方法。
(答案是反向给出的!)

谢谢您的回复! - VisioN

1
这是我的解决方案。一般策略如下:
- 如果数字为负数,则使用2的补码取反,并在最后加上负号 - 将任意大小的数字表示为0到9的数字的LE数组 - 对于Uint8Array中的每个字节(从最高位到最低位),将运行总数乘以256并将其添加到新字节的值中 - 要将一个数字乘以256,将其翻倍8次(因为2 ** 8 == 256) - 要求两个数字的和,使用小学算法:
- 从最低有效数字开始 - 添加两个数字的相应数字 - 结果数字是模10的余数;如果和大于或等于10,则进位为1,否则为0 - 继续使用进位加上相应的数字,直到我们添加了最高有效数字且进位为0
关于速记的几点说明:
  • n1[i] || 0 获取n1的第i位数字。如果超出了i的范围,我们将其视为0(想象一下用无限的0来表示数字)。n2同理。
  • added > 9生成一个布尔值,自动转换为数字(如果added >= 10则为1,否则为0)
  • i < n1.length || i < n2.length || carry检查加数或进位是否还有更多数字
  • String(b).split('').map(Number).reverse()将例如100转换为'100',然后是['1', '0', '0'],然后是[1, 0, 0],最后是[0, 0, 1],因此它以LE基数10表示
  • result.reverse().join('')将例如[0, 0, 1]转换为[1, 0, 0],然后是'100'

代码:

function add(n1, n2) {
    const sum = []
    let carry = 0
    for (let i = 0; i < n1.length || i < n2.length || carry; i++) {
        const added = (n1[i] || 0) + (n2[i] || 0) + carry
        sum[i] = added % 10
        carry = added > 9 //floor(added / 10)
    }
    return sum
}
function times256(n1) {
    for (let i = 8; i; i--) n1 = add(n1, n1)
    return n1
}
function toString(buffer) {
    const isNegative = buffer[0] & 128 //check if high bit is set
    if (isNegative) { //convert to positive, using 2's complement
        buffer = buffer.map(b => ~b) //invert all bits
        let i = buffer.length - 1
        while (buffer[i] === 255) { //add 1 to the number, carrying if necessary
            buffer[i] = 0
            i--
        }
        buffer[i]++
    }
    const result = buffer.reduce((sum, b) =>
        add(
            times256(sum), //multiply sum by 256
            String(b).split('').map(Number).reverse() //then add b
        ),
        []
    )
    const stringResult = result.reverse().join('')
    if (isNegative) return '-' + stringResult
    else return stringResult
}

非常感谢您的回复。您的代码和解释非常出色。现在我想知道哪种解决方案更好:您的还是Stephan的?(https://dev59.com/caPia4cB1Zd3GeqP6vqP#45505770)。他的解决方案更短,只包含两个循环,而您的策略更详细、更清晰。我们可能需要进行一些性能测试。 - VisioN
是的,我确定他的可能更快,但我觉得这个更容易理解。 - csander

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接