8000 C/C++实现64位整数输出 · Issue #56 · dongjun111111/blog · GitHub
[go: up one dir, main page]

Skip to content

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

Open

Description

@dongjun111111

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      0