分类导航

C&C++ 发布时间：2022-04-03 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了将二进制转换为十进制的最快方法？，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

我有四个无符号的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;
            }
        }
    }
}

解决方法

这取决于你对数字做了什么.您可以牺牲空间效率的轻微损失和多精度算术效率的适度损失,以换取非常有效的十进制转换.关键是使用10的幂而不是2的幂来进行多精度算术.

例如,您可以使用10,000的基数,将一个数字打包成16位字,然后对32位整数的数字进行算术运算. (如果您使用的是64位计算机,则可以将其加倍并基于1,000,000.)这种代码在时间上相对有效,但不如使用2的本机功能快,因为您无法利用硬件上的进位.
而且你不能用相同的位数来表示那么多的整数.
但它是转换为十进制和从十进制转换的高手,因为您可以转换单个数字而无需任何长除法.

如果您需要表示从零到((1 << 128) - 1)的全部数字范围,您仍然可以执行此操作,但添加一个额外的数字,因此您的数字会更大. 如果事实证明你真的需要额外的空间/速度(也许你正在进行大量的加密128位计算)那么同步div / mod by 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;
}

为了充分理解,获得本书确实很有帮助,但source code仍然比GNU源代码更容易理解.并且您可以轻松地将其调整为使用10,000(当前使用256基础).

简介：如果您的性能瓶颈是转换为十进制,请使用10的幂来实现多精度算法.如果您的机器的本机字大小为32并且您使用的是C代码,则在16位字中使用10,000.