1

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

typedef struct {
    uint64_t low, high;
} uint128;

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

现在我想打印一个以 10 为底的值，使用printf. 我可能需要除以 10 才能做到这一点，但还没有实现除法。

我怎样才能做到这一点？该解决方案不必非常高效，只要它有效。

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

4

4 回答 4

3 
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]);
}
于 2010-12-06T08:10:49.247 回答
3

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

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

编辑：这是一个示例（它将short仅使用算术打印 a 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;
};

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

于 2010-12-05T22:25:05.607 回答
2

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

这是一种方法，首先除以 10 20得到不大于 3,402,823,669,209,384,634 的商。然后我们将余数（本身不大于 10 20）除以 10 10得到另一个商和余数，每个都小于 10 20，它们都适合 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);
}
于 2010-12-05T22:48:01.183 回答
1

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

  1. 由于 2 128大约是 340E36，首先通过与 100E36、200E36 和 300E36 边界比较数字来确定前导数。写一个数字并减去最近的较小边界。例如。如果数字是 234.6776E36，那么最近的较小边界是 200E36，数字是“2”，减法后你应该得到 34.6776E36。

  2. 现在使用与数字 10E36...90E36 的比较来获得下一个数字。当然是128位比较。写一个数字并减去上面的小边界。（对于 34.6776E36 上面的数字是 '3'，边界是 30E36，余数是 4.6776E36）

  3. 然后将数字乘以 10 并从第 2 阶段重复，总共打印 38 次以打印每个数字。(4.6776E36 -> 46.776E36...)

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

UPD2：第一个数字需要专门的步骤是因为如果你乘它旁边的数字，你应该得到溢出，如果余数大于 34E36。

于 2010-12-06T09:21:37.907 回答