C：打印一个以 10 为基数的 BigInteger

发布于 2024-10-06 11:31:08 字数 294 浏览 4 评论 0原文

我正在使用这个结构来表示 128 位整数：（

typedef struct {
    uint64_t low, high;
} uint128;

除非你能给我指出一个快速的 128 位整数库，否则我无法更改它）

现在我想使用 printf 打印这样一个以 10 为基数的值。我可能需要除以 10 才能做到这一点，但尚未实现除法。

我该怎么做？该解决方案不必非常高效，只要它有效即可。

编辑：我喜欢你提出的所有解决方案。你太棒了。

原文

I am using this struct to represent 128bit integers:

typedef struct {
    uint64_t low, high;
} uint128;

(Unless you can point me to a fast 128bit integer library I can not change that)

Now I want to print such a value in base 10, using printf. I probably need division by 10 to do that, but no division is implemented yet.

How can I do this? The solution does not have to be super efficient, as long as it works.

EDIT: I like all solutions you came up with. You are awesome.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

甜味超标? 2024-10-13 11:31:08

void printu128(uint128 n) {
  int d[39] = {0}, i, j;
  for (i = 63; i > -1; i--) {
    if ((n.high >> i) & 1) d[0]++;
    for (j = 0; j < 39; j++) d[j] *= 2;
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10;
  }
  for (i = 63; i > -1; i--) {
    if ((n.low >> i) & 1) d[0]++;
    if (i > 0) for (j = 0; j < 39; j++) d[j] *= 2;
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10;
  }
  for (i = 38; i > 0; i--) if (d[i] > 0) break;
  for (; i > -1; i--) putchar('0'+d[i]);
}

void printu128(uint128 n) {
  int d[39] = {0}, i, j;
  for (i = 63; i > -1; i--) {
    if ((n.high >> i) & 1) d[0]++;
    for (j = 0; j < 39; j++) d[j] *= 2;
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10;
  }
  for (i = 63; i > -1; i--) {
    if ((n.low >> i) & 1) d[0]++;
    if (i > 0) for (j = 0; j < 39; j++) d[j] *= 2;
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10;
  }
  for (i = 38; i > 0; i--) if (d[i] > 0) break;
  for (; i > -1; i--) putchar('0'+d[i]);
}

回复收藏 0 原文

撞了怀 2024-10-13 11:31:08

如果您不想实现 128 位值的除法，您可以预先计算几个（~40）代表 10 次幂的 128 位值，并使用减法。

实际上只有较高的 qword 才会以这种方式处理，因为对于较低的部分，您可以使用 printf("%I64d")。

编辑：这是一个示例（它将仅使用 char 上的算术打印 short）：

unsigned char pow10[][2] = {
    {0,   1},   // 1
    {0,  10},   // 10
    {0, 100},   // 100
    {3, 0xE8},  // 1k
    {0x27, 0x10}};  // 10k == 0x2710

#define HIGH 0
#define LOW  1

void print_dec(unsigned char H, unsigned char L){
    unsigned char L1;
    int pwr = 4, ctr = 0;
    while (pwr >= 0){
        int c = pow10[pwr][LOW] > L;
        L1 = L - pow10[pwr][LOW];
        if (H >= pow10[pwr][HIGH] + c){     
            H -= pow10[pwr][HIGH] + c;
            L = L1;
            ctr++;
        } else {
            printf("%d", ctr);
            ctr = 0;
            pwr--;
            //here we could add a check for H to be 0, so that we could use
            //printf() for lower half. we just have to be careful with 
            //leading zeroes in L, the simpliest way is to use printf("%03d",L)
        };
    };
    printf("\n");
};

int main(){
    unsigned short n = 12345;
    printf("%d should be ", n);
    print_dec((n >> 8) & 0xFF, n & 0xFF);
    return 0;
};

您可以使用较少数量的预先计算的 10 次幂，但这会使速度变慢（例如，以 100 为步长将使 ctr 处于 0..99 范围内。

If you don't want to implement division for 128bit value, you could precompute several (~40) 128 bit values that represents powers of 10, and use substraction.

Actually only higher qword have be processed in this way, because for lower part you can use printf("%I64d").

EDIT: here is an example (it will print a short using only arithmetics on char):

unsigned char pow10[][2] = {
    {0,   1},   // 1
    {0,  10},   // 10
    {0, 100},   // 100
    {3, 0xE8},  // 1k
    {0x27, 0x10}};  // 10k == 0x2710

#define HIGH 0
#define LOW  1

void print_dec(unsigned char H, unsigned char L){
    unsigned char L1;
    int pwr = 4, ctr = 0;
    while (pwr >= 0){
        int c = pow10[pwr][LOW] > L;
        L1 = L - pow10[pwr][LOW];
        if (H >= pow10[pwr][HIGH] + c){     
            H -= pow10[pwr][HIGH] + c;
            L = L1;
            ctr++;
        } else {
            printf("%d", ctr);
            ctr = 0;
            pwr--;
            //here we could add a check for H to be 0, so that we could use
            //printf() for lower half. we just have to be careful with 
            //leading zeroes in L, the simpliest way is to use printf("%03d",L)
        };
    };
    printf("\n");
};

int main(){
    unsigned short n = 12345;
    printf("%d should be ", n);
    print_dec((n >> 8) & 0xFF, n & 0xFF);
    return 0;
};

You can use smaller number of precomputed powers of 10, but it will make it slower (ex, having them in steps of 100 will make ctr to be in range 0..99.

回复收藏 0 原文

提赋 2024-10-13 11:31:08

假设您已经实现了对 uint128 执行数学计算的函数，您可以将数字分成 3 部分并使用 printf 的内置 64 位打印功能。由于最大的 64 位数字有 20 位长，这意味着所有 19 位十进制数都可以这样打印，但由于最大的 128 位数字有 39 位长，所以我们不能将其分成两部分，因为我们最终得到的 20 位数字可能比最大的 64 位数字大。

这是一种方法，首先除以 10²⁰ 以获得不大于 3,402,823,669,209,384,634 的商。然后，我们将余数（本身不大于 10²⁰）除以 10¹⁰，得到另一个商，余数均小于 10²⁰，即两者都适合 64 位整数。

void print_uint128(uint128 value)
{
    // First power of 10 larger than 2^64
    static const uint128 tenToThe20 = {7766279631452241920ull, 5ull};
    static const uint128 tenToThe10 = {10000000000ull, 0ull};

    // Do a 128-bit division; assume we have functions to divide, multiply, and
    // subtract 128-bit numbers
    uint128 quotient1 = div128(value, tenToThe20);
    uint128 remainder1 = sub128(value, mul128(quotient, tenToThe20));
    uint128 quotient2 = div128(remainder1, tenToThe10);
    uint128 remainder2 = sub128(remainder1, mul128(remainder1, tenToThe10));

    // Now print out theresult in 3 parts, being careful not to print
    // unnecessary leading 0's
    if(quotient1.low != 0)
        printf("%llu%010llu%010llu", quotient1.low, quotient2.low, remainder2.low);
    else if(quotient2.low != 0)
        printf("%llu%010llu", quotient2.low, remainder2.low);
    else
        printf("%llu", remainder2.low);
}

Assuming you've already implemented functions to perform math on uint128, you could break the number up into 3 parts and use the built-in 64-bit printing capabilities of printf. Since the largest 64-bit number is 20 digits long, that means all 19-digit decimal numbers can be printed that way, but since the largest 128-bit number is 39 digits long, we can't break it up into only 2 parts, since there's a chance that we might end up with a 20 digit number bigger than the largest 64-bit number.

Here's one way to do it, dividing first by 10²⁰ to get a quotient no larger than 3,402,823,669,209,384,634. We then divide the remainder (itself no larger than 10²⁰) by 10¹⁰ to get another quotient and remainder each less than 10²⁰, which both fit in a 64-bit integer.

void print_uint128(uint128 value)
{
    // First power of 10 larger than 2^64
    static const uint128 tenToThe20 = {7766279631452241920ull, 5ull};
    static const uint128 tenToThe10 = {10000000000ull, 0ull};

    // Do a 128-bit division; assume we have functions to divide, multiply, and
    // subtract 128-bit numbers
    uint128 quotient1 = div128(value, tenToThe20);
    uint128 remainder1 = sub128(value, mul128(quotient, tenToThe20));
    uint128 quotient2 = div128(remainder1, tenToThe10);
    uint128 remainder2 = sub128(remainder1, mul128(remainder1, tenToThe10));

    // Now print out theresult in 3 parts, being careful not to print
    // unnecessary leading 0's
    if(quotient1.low != 0)
        printf("%llu%010llu%010llu", quotient1.low, quotient2.low, remainder2.low);
    else if(quotient2.low != 0)
        printf("%llu%010llu", quotient2.low, remainder2.low);
    else
        printf("%llu", remainder2.low);
}

回复收藏 0 原文

萤火眠眠 2024-10-13 11:31:08

您可以使用乘法来打印数字。

由于 2¹²⁸ 约为 340E36，因此首先通过将数字与 100E36、200E36 和 300E36 边界进行比较来确定前导数字。写入一个数字并减去最近的较小边界。例如如果数字是 234.6776E36，那么最近的较小边界是 200E36，数字是“2”，相减后应该得到 34.6776E36。
现在通过与数字 10E36...90E36 进行比较来获取下一个数字。当然是128位比较。如上所述，写入一个数字并减去最小边界。（对于 34.6776E36，上面的数字是“3”，边界是 30E36，余数是 4.6776E36）
然后将数字乘以 10，并从阶段 2 开始重复，总共 38 次打印每个数字。 (4.6776E36 -> 46.776E36...)

UPD：添加了我首先错过的减法。以及例子。

UPD2：第 1 位数字需要专用步骤，因为如果将其旁边的数字相乘，如果余数大于 34E36，则应该会溢出。

回复收藏 0 原文

~没有更多了~