将二进制转换为十进制的最快方法是什么？

Question

我有四个未签名的32位整数，表示一个无符号的128位整数，按照小端顺序：

typedef struct {
    unsigned int part[4];
} bigint_t;

我想将这个数字转换为它的十进制字符串表示，并将其输出到文件中。目前，我正在使用一个bigint_divmod10函数将数字除以10，并跟踪余数。我重复调用此函数，将余数作为数字输出，直到数字为零。这很慢。这是最快的方法吗？如果是，是否有一种聪明的方法来实现这个函数，而我没有看到？我尝试查看GMP的get_str.c，但我觉得它非常难以理解。编辑：这里是我能想出的divmod10函数的最快代码：

static unsigned uint128_divmod10(uint128 *value)
{
    unsigned int a = value->word[3];
    unsigned int b = value->word[2];
    unsigned int c = value->word[1];
    unsigned int d = value->word[0];

    unsigned int diva = a / 5;
    unsigned int divb = b / 5;
    unsigned int divc = c / 5;
    unsigned int divd = d / 5;

    value->word[3] = diva;
    value->word[2] = divb;
    value->word[1] = divc;
    value->word[0] = divd;

    unsigned int moda = a - diva*5;
    unsigned int modb = b - divb*5;
    unsigned int modc = c - divc*5;
    unsigned int modd = d - divd*5;

    unsigned int mod = 0;
    mod += moda;
    unsigned int carryb = mod*858993459;
    mod += modb;
    if (mod >= 5) {
        mod -= 5;
        carryb++;
    }
    unsigned int carryc = mod*858993459;
    mod += modc;
    if (mod >= 5) {
        mod -= 5;
        carryc++;
    }
    unsigned int carryd = mod*858993459;
    mod += modd;
    if (mod >= 5) {
        mod -= 5;
        carryd++;
    }

    uint128_add(value, carryd, 0);
    uint128_add(value, carryc, 1);
    uint128_add(value, carryb, 2);

    if (value->word[0] & 1) {
        mod += 5;
    }
    uint128_shift(value, -1);
    return mod;
}

add函数的定义如下:

static void uint128_add(uint128 *value, unsigned int k, unsigned int pos)
{
    unsigned int a = value->word[pos];
    value->word[pos] += k;
    if (value->word[pos] < a) {
        // overflow
        for (int i=pos+1; i<4; i++) {
            value->word[i]++;
            if (value->word[i]) {
                break;
            }
        }
    }
}

- ianh

---

为什么不使用十六进制而是使用十进制字符串表示？转换为十六进制更快。 - Test

你确定这对你的程序非常关键，值得你花时间调整它，而且你的继任者也要理解这个混乱吗？ - vonbrand

Answer 1

这取决于你对数字的其他处理方式。为了实现非常高效的十进制转换，你可以在空间效率略有损失和多精度算术效率适度损失之间进行权衡。关键是使用以10为底数而不是以2为底数进行多精度算术运算。例如，您可以使用基数10000，其中一个数字打包到16位字中，并在32位整数上执行算术运算。(如果您使用的是64位机器，则可以将其加倍并使用基数1000000000。) 这种代码相对而言时间效率较高，尽管不像使用本机二进制快，因为您无法利用硬件上的进位位。并且您不能在相同位数的情况下表示更多的整数。但是在转换为和从十进制的时候效果很好，因为您可以转换单个数字而不需要进行长除法。如果您需要表示从零到((1 << 128)-1)的所有数字范围，仍然可以做到这一点，但需要添加一个额外的数字，因此您的数字将更大。

如果您确实需要额外的空间/速度（也许您正在进行大量的128位加密计算），那么我知道的最快方法是同时除以10进行模运算的方法。另一个技巧是，如果小整数很常见，您可以特别处理它们。（也就是说，如果前三个最高32位字都为零，则只需使用本地除法进行转换。）

“有没有一种聪明的方法来实现这个函数，我没有看到？”

Dave Hanson的C Interfaces and Implementations有一个关于多精度算术的章节。将大数除以单个数字是一种特殊情况，具有高效的实现方式：

int XP_quotient(int n, T z, T x, int y) {
    int i;
    unsigned carry = 0;
    for (i = n - 1; i >= 0; i--) {
        carry = carry*BASE + x[i];
        z[i] = carry/y;
        carry %= y;
    }
    return carry;
}

为了充分理解，拥有这本书真的会很有帮助，但源代码仍然比GNU源代码容易理解得多。你可以很容易地将其适应使用10,000进制（它目前使用的是256进制）。

总结：如果您的性能瓶颈是十进制转换，请实现一个基数是10的幂的多精度算术。如果您的机器本地字大小为32并且您正在使用C代码，请在16位字中使用10,000。

- Norman Ramsey

Answer 2

如果您的值大多小于ULLONG_MAX（18446744073709551615），我建议使用sprintf(buf,"%llu",ullong_val)来处理它们。我敢打赌，这在标准库中已经得到了很好的优化，但格式解析可能需要一些时间。

否则，我会创建一个bigint_divmod1000000000（或更好的名称mod10to9）函数并使用它。相比bigint_divmod10，它需要少九倍的除法运算。

- Tometzky

---

像那样的大型divmod函数实际上更慢（我尝试过）。 - ianh

Answer 3

8位查找表。 您可以有4个256数字的查找表。 第一个表是0-256的LSB字节，第二个表是第一个表乘以256，以此类推。

因此，当您需要您的数字时，请从查找表中累加数字。 当您添加时，您可以将其作为二进制数相加，稍后再通过每个字节进行一次修复以解决溢出问题。

例如 数字0x12345678 在第一个查找表下，地址为（0x78 = 120） 所以第一个数字是0x010200 在第二个表中，地址为（0x56 = 87），为0x0202000106（十进制中的0x56为22016） 在第三个表中，您会得到0x03040007080702 在最后一个标签下，0x12中的值为0x030001090809080808（这不适合32位算术，但您已经知道了）

然后将这些数字相加（作为二进制数），并逐个字节逐个通过溢出进行一遍修复 for循环中的代码类似于：

s=carry+val[i];
val[i]=val[i]&10
carry=s/10; 
//you can put last two operations in table

如果我们计算这个过程所需的操作。

1.（查找表格和加法）4个查找表。16次加法（请记住，当您不需要考虑溢出时，因为它们不能发生）
2.每个步骤一次遍历3次操作，16个步骤需要通过。

悲观的上限是6 * 16 = 100次操作。

编辑：

这是c++代码，并且比朴素实现快30％。

#include <iostream>
#include <stdint.h>
#include <array>

static uint64_t lu[4][256];

constexpr uint64_t lookup_value(uint64_t n) {
  uint64_t r = 0;
  uint64_t t = 1;
  while (n) {
    uint64_t rem = n % 10;
    n /= 10;
    r += rem * t;
    t *= 256;
  }
  return r;
}

void make_lu() {
  uint64_t step = 1;
  for (int j = 0; j < 4; ++j) {
    uint64_t n = 0;
    for (int i = 0; i < 256; ++i) {
      lu[j][i] = lookup_value(n);
      n += step;
    }
    step *= 256;
  }
}

struct DivMod {
  uint8_t div;
  uint8_t rem;
};

static DivMod dm[256];

void make_dm() {
  for (int i = 0; i < 256; ++i) {
    dm[i].div = i / 10;
    dm[i].rem = i % 10;
  }
}

void init() {
  make_lu();
  make_dm();
}

uint64_t b2d(uint64_t n) {
  uint64_t r = 0;
  for (int i = 0; i < 4; ++i) {
    r += lu[i][(n >> (i * 8)) & 0xff];
  }
  uint64_t r2 = 0;
  uint64_t of = 0;
  for (int i = 0; i < 8; ++i) {
    uint64_t v = ((r >> (i * 8)) & 0xff) + of;
    DivMod &x = dm[v];
    of = x.div;
    r2 += uint64_t(x.rem) << (i * 8);
  }
  return r2;
}

int main() {
  init();
  uint64_t n;
  std::cin >> n;
  std::cout << std::hex << b2d(n) << "\n";
  return 0;
}

- Luka Rahne

---

问题中的数字是128位的；如果我错了，请纠正我，但是你的答案似乎假设了32位的数字。 - ianh

据我所知，我的假设是正确的。 在第一步中，您使用查找表进行了4次128位数字的加法（总共16次加法），实际上少了一点，因为您知道LSB字节不超过32位。因此，对于LSB字节，只需要进行一次加法而不是四次。我发现错误并在解释中进行了更改。而不是0x120，应该是0x010200。 - Luka Rahne

val[i] & 10（按位与 0b1010）没有意义。它不是余数。移位/掩码仅适用于基数为2的幂，例如十六进制或八进制。最低有效的十进制数字取决于所有位，因此查找表根本不起作用。 - Peter Cordes

@PeterCordes 这是正确的。主要观点是只需要在小表中进行添加和查找。 - Luka Rahne

我不确定你的算法是如何工作的。你的回答没有很好地解释清楚。我不明白为什么你要使用十六进制数字，而OP想要一个十进制字符串。你是在构建一个二进制数，其十六进制位具有原始数字的十进制位的值吗？我也不明白你的循环变量的类型是什么。例如，s是BigInteger吗？（足够大，可以容纳与输出具有相同十进制位数的十六进制位数？）val[]是什么类型？ - Peter Cordes

@PeterCordes 为了实现矢量化，使用32位数字。首先将长二进制数拆分成8位块（字节）。然后每个字节根据索引和表示为十进制数的值而不同。这些可以从查找表中读取。我们将这些数字相加并最终修复溢出。最终解决方案仅使用加法和查找表，而没有分支（if语句）。我不确定它与其他优化解决方案相比如何。 - Luka Rahne

Answer 4

为了以后的参考，我没有实现uint128类型，而是直接使用字符串的字符。结果证明，这比从字符串转换到uint128再转回来要快得多。

- ianh

---

如果在转换为字符串之前只执行几个操作，那么这是有意义的。使用10^9进制的32位块可以很好地工作，并且在加法/减法与除以（10的幂次方）之间取得良好的平衡。我使用了这种方法在合理的时间内（约80秒）计算出Fibonacci（10 ^ 9）的前1000位数字，在每一步中仅保留前导1009位数字，使用除以10。只有105字节的x86代码，使用比较生成进位并在10^9处进行包装。 :) - Peter Cordes

Answer 5

我知道这个问题很老了，但是我想贡献一下，因为没有人提出避免除法周期的方法。这个方法使用pow2，虽然我还没有测试过基准性能，但理论上应该比其他任何方法都要快，并且也可以在pow函数中进行调整。

#include <iostream>
#include <cmath>
using namespace std;

#define MathBintodec(arr,len)({int dec=0;int ci_;for(ci_=len;ci_--;)dec+=arr[ci_]*pow(2,len-ci_-1);dec;})

int main(){
    int r[]={1,0,0,1,0,0};
    cout<<MathBintodec(r,6)<<endl;
}

输出： 36

- superbem

---

你正在将一个基于位置的数组转换为二进制整数（而且效率非常低）。OP想要高效地将uint128_t转换为字符串。 - Peter Cordes

Answer 6

最直接的加速将来自于内联转换而不是调用函数；这可能只需要将bigint_divmod10()标记为内联，或使用编译器提供的基于性能分析的优化。

- Will