字节数组到 Uint64 作为字符串
Byte Array to Uint64 as a String
让我们考虑以下情况。
Go 例程创建一个字节数组，其中将 Uint64 数字 5577006791947779410 打包成 8 个字节 Big Endian [77, 101, 130, 33, 7, 252, 253, 82].
在 JavaScript 代码中，我收到这些字节作为 Uint8Array。我们知道 JavaScript 目前不支持 Uint64 作为安全数字类型并且不能对大于 32 位的整数执行按位运算，所以像 buf[0] << 56 这样的东西永远不会工作。
那么将这些字节直接解码为数字字符串的过程是怎样的"5577006791947779410"？
P.S. 我知道 JavaScript 中有 plenty of libraries 用于处理大整数，但通常它们很大并且提供很多数学运算，我在这里不需要。我正在寻找一种简单的现代直接解决方案，用于 just 解码 BE-packed Uint64 和 Int64 字节到数字字符串。你有什么想法吗？
编辑： 对于转换 (U)int64 我现在绝对推荐@LS_DEV 的解决方案。只有当字节数未知或更大时，我才会使用我的解决方案。
我是从开始修改的：
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 并计算下一个数字的开销 (byte - digits[i]) / 10 和 Math.floor(byte / 10)）。对于下一个字节，必须添加最后一个字节数字的移位结果（byte += digits[i] * 256 resp. digits[i] << 8）。
该代码针对短小、简单和灵活进行了优化。如果您使用的是字符串而不是字节或数字，并且不想使用任何库，那么转换性能似乎并不重要。否则该函数可以针对性能进行优化：最多可以同时处理四个字节，一个只需要替换 0x100 和 0x80，另外（在 ( U)Int64) forEach 循环可以展开。对十进制数字进行分组可能不会提高性能，因为生成的字符串必须用零填充，从而需要在最终结果中删除前导零。
这是我的解决方案。总体策略是这样的：
- 如果数字是负数，使用 2 的补码取反并在末尾添加负号
- 将任意大小的数字表示为从 0 到 9 的 LE 数字数组
- 对于
Uint8Array 中的每个字节（从最重要到最不重要），将 运行 总和乘以 256，然后加上新字节的值
- 要将一个数乘以 256，将其乘以 8 次（因为
2 ** 8 == 256）
- 两个数相加，用小学算法：
- 从最低有效数字开始
- 将两个数的对应数字相加
- 结果数字是总和mod10；如果总和为 10 或更多，则进位为 1，否则为 0
- 继续将相应的数字与进位相加，直到我们添加最高有效位且进位为0
关于shorthand的几点说明：
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 base-10result.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
}
这是 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()函数returns一个'full'8位的二进制数，所以我们可以创建'fnl'为64位的BigEndian字符串。
由于 JavaScript 不进行完整的 64 位运算，我创建了 dec[] 数组以将 2 的每个幂存储为单独的数字，方法是将每个前面的数字加倍并平滑十位.
接下来就是把我们想要的位相加，也就是用类似的方法来平滑十位。
（而且答案是倒着写的！）
另一种方法：将问题分成两个 uint32 以使计算易于管理。
考虑更低和更高的 uint32（l 和 h）。完整的数字可以写成h*0x100000000+l。考虑到十进制，还可以考虑低 9 位和剩余的高位（ld 和 hd）：ld=(h*0x100000000+l)%1000000000 和 hd=(h*0x100000000+l)/1000000000。使用一些算术和代数运算符属性，可以将这些运算分解为安全的 "half" 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，算法仍然有效，因为丢失的位仍然为零。
让我们考虑以下情况。
Go 例程创建一个字节数组，其中将 Uint64 数字 5577006791947779410 打包成 8 个字节 Big Endian [77, 101, 130, 33, 7, 252, 253, 82].
在 JavaScript 代码中，我收到这些字节作为 Uint8Array。我们知道 JavaScript 目前不支持 Uint64 作为安全数字类型并且不能对大于 32 位的整数执行按位运算，所以像 buf[0] << 56 这样的东西永远不会工作。
那么将这些字节直接解码为数字字符串的过程是怎样的"5577006791947779410"？
P.S. 我知道 JavaScript 中有 plenty of libraries 用于处理大整数，但通常它们很大并且提供很多数学运算，我在这里不需要。我正在寻找一种简单的现代直接解决方案，用于 just 解码 BE-packed Uint64 和 Int64 字节到数字字符串。你有什么想法吗？
编辑： 对于转换 (U)int64 我现在绝对推荐@LS_DEV 的解决方案。只有当字节数未知或更大时，我才会使用我的解决方案。
我是从开始修改的：
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 并计算下一个数字的开销 (byte - digits[i]) / 10 和 Math.floor(byte / 10)）。对于下一个字节，必须添加最后一个字节数字的移位结果（byte += digits[i] * 256 resp. digits[i] << 8）。
该代码针对短小、简单和灵活进行了优化。如果您使用的是字符串而不是字节或数字，并且不想使用任何库，那么转换性能似乎并不重要。否则该函数可以针对性能进行优化：最多可以同时处理四个字节，一个只需要替换 0x100 和 0x80，另外（在 ( U)Int64) forEach 循环可以展开。对十进制数字进行分组可能不会提高性能，因为生成的字符串必须用零填充，从而需要在最终结果中删除前导零。
这是我的解决方案。总体策略是这样的：
- 如果数字是负数，使用 2 的补码取反并在末尾添加负号
- 将任意大小的数字表示为从 0 到 9 的 LE 数字数组
- 对于
Uint8Array中的每个字节（从最重要到最不重要），将 运行 总和乘以 256，然后加上新字节的值 - 要将一个数乘以 256，将其乘以 8 次（因为
2 ** 8 == 256） - 两个数相加，用小学算法：
- 从最低有效数字开始
- 将两个数的对应数字相加
- 结果数字是总和mod10；如果总和为 10 或更多，则进位为 1，否则为 0
- 继续将相应的数字与进位相加，直到我们添加最高有效位且进位为0
关于shorthand的几点说明：
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 base-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
}
这是 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()函数returns一个'full'8位的二进制数，所以我们可以创建'fnl'为64位的BigEndian字符串。
由于 JavaScript 不进行完整的 64 位运算，我创建了 dec[] 数组以将 2 的每个幂存储为单独的数字，方法是将每个前面的数字加倍并平滑十位.
接下来就是把我们想要的位相加，也就是用类似的方法来平滑十位。
（而且答案是倒着写的！）
另一种方法：将问题分成两个 uint32 以使计算易于管理。
考虑更低和更高的 uint32（l 和 h）。完整的数字可以写成h*0x100000000+l。考虑到十进制，还可以考虑低 9 位和剩余的高位（ld 和 hd）：ld=(h*0x100000000+l)%1000000000 和 hd=(h*0x100000000+l)/1000000000。使用一些算术和代数运算符属性，可以将这些运算分解为安全的 "half" 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，算法仍然有效，因为丢失的位仍然为零。