C/C++实现64位整数输出

高精度整数是常见的问题之一。但实际上有的时候只是需要比现有整数精度高一点。比如需要128位整数，256位整数等。这个时候就有可能比起去写任意精度整数而言，针对特殊需求写比较好。因为位数比较少，所以好的方式是模仿现有的整数存储方式去实现，用二进制存储。这里面比较麻烦的一步就是输出，因为输出需要写成十进制数，但运算和存储都是二进制形式。于是我自己实现了一个64位整数的输出作为练习。实现64位的原因是为了便于和原有的64位整数输出效率进行对比。这里面的基本思想就是用两个unsigned int来拼成一个64位整数，它们分别存储前32位和后32位，记为a和b，存储策略同已有的整数类型。输出的时候每次对a_2^32+b除以10000，余数为最末4位，然后循环得到所有十进制位。用10000应该是最好的选择，使用100000会在计算过程中溢出。计算a_2^32+b除以10000的时候将a和2^32分别考虑即可。如果是负数，则事先将其取反+1，化成相反数即可。此外还需要注意一些边界情况即可。对于一般的整数，自测大约比系统的输出要慢一倍，特殊的整数会比系统的略快（例如-1）。

#include 

const unsigned int t = 10000;
const unsigned int u1 = 429496;
const unsigned int u2 = 7296;

void output(unsigned int a, unsigned int b) {
    unsigned int r[128];
    int p = 0;
    bool negative = false;

    if (a >= 0x80000000) {
        negative = true;
        if (a == 0x80000000 && b == 0) {
            printf("-9223372036854775808\n");
            return;
        }
        if (b != 0) {
            b = (~b) + 1;
            a = ~a;
        }
        else {
            a = (~a) + 1;
        }
    }

    while (a > 0 || b > 0) {
        unsigned int a2 = a % t;
        unsigned int b2 = b % t;
        unsigned int c = a2 * u2 + b2;
        unsigned int d = c / t;

        r[p++] = c - d * t;

        a /= t;
        b /= t;

        b += a2 * u1 + d;
    }

    if (negative) {
        printf("-");
    }

    if (p == 0) {
        printf("0");
    }
    else {
        printf("%d", r[--p]);
        while (p > 0) {
            printf("%04d", r[--p]);
        }
    }
    printf("\n");
}

int main() {
    long long c_array[] = {0x8000000000000000ll, 0xffffffffffffffffll,
        0x7fffffffffffffffll, 0x0000000000000000ll, 0x7fffffff7fffffffll,
        0x0000000000000001ll, 0x1234567890abcdefll};
    for (int i = 0; i < sizeof(c_array) / sizeof(c_array[0]); i++) {
        long long c = c_array[i];
        printf("%lld\n", c);
        output(c >> 32, c & 0xffffffff);
    }
    return 0;
}

参考

http://diaorui.net/archives/257

dongjun111111 / blog

C/C++实现64位整数输出 #56

C/C++实现64位整数输出

参考