Массив байтов в Uint64 в виде строки

EDIT: Для преобразования (U)int64 теперь я определенно рекомендую решение @LS_DEV. Я бы использовал свое решение только при наличии неизвестного или большего количества байтов.

Я начал с https://stackoverflow.com/a/21668344/3872370 и изменил его:

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 соответственно digits[i] << 8).

Этот код оптимизирован для краткости, простоты и гибкости. Если вы работаете со строками, а не с байтами или числами, и не хотите использовать какие-либо библиотеки, то производительность преобразования не имеет большого значения. В противном случае функция может быть оптимизирована для повышения производительности: одновременно может обрабатываться до четырех байтов, нужно только заменить 0x100 и 0x80, кроме того (с оставшимися только двумя группами байтов в случае (U)Int64) цикл forEach может быть развернутым. Группировка десятичных цифр, вероятно, не повысит производительность, так как результирующие строки должны быть дополнены нулями, что приводит к необходимости удаления начальных нулей в конечном результате.

Другой подход: разделить задачу на два uint32, чтобы расчеты оставались управляемыми.

Рассмотрим более низкий и более высокий uint32 (l и h). Полный номер может быть записан как h*0x100000000+l. Учитывая десятичную дробь, можно также рассмотреть младшие 9 цифр и оставшиеся старшие цифры (ld и hd): ld=(h*0x100000000+l)%1000000000 и hd=(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, потому что потерянные биты, тем не менее, равны нулю.

Вот мое решение. Общая стратегия такова:

• Если число отрицательное, инвертируйте его, используя дополнение до 2, и добавьте отрицательный знак обратно в конце.
• Представляйте числа произвольного размера как массивы LE цифр от 0 до 9
• Для каждого байта в Uint8Array (от наиболее значимого к наименее значимому) умножьте промежуточную сумму на 256 и добавьте к ней значение нового байта.
• Чтобы умножить число на 256, удвойте его 8 раз (начиная с 2 ** 8 == 256)
• To add two numbers, use the elementary school algorithm:
  • Start with least significant digit
  • Сложите соответствующие цифры двух чисел
  • Результирующая цифра представляет собой сумму по модулю 10; перенос равен 1, если сумма больше 10, иначе 0
  • Продолжайте добавлять соответствующие цифры с переносом, пока мы не добавим самые значащие цифры, а перенос не станет равным 0.

Несколько замечаний по стенографии:

• n1[i] || 0 получает i цифру n1. Если это конец i, мы рассматриваем его как 0 (представьте числа, представленные с бесконечными нулями перед ними). То же самое с n2.
• added > 9 создает логическое значение, которое автоматически преобразуется в число (1, если added >= 10, 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() возвращает «полное» 8-битное двоичное число, поэтому мы можем создать «fnl» как 64-битную строку BigEndian.

Поскольку JavaScript не выполняет полные 64-битные арифметические операции, я создаю массив dec[] для хранения каждой степени двойки в виде отдельных цифр, удваивая каждую предыдущую цифру и сглаживая десятки.

Затем остается только добавить нужные нам биты, используя аналогичный метод для сглаживания десятков.

(и ответ дан в обратном порядке!)