C：在基地打印的BigInteger 10

我使用這個結構來表示128bit的整數：C：在基地打印的BigInteger 10

typedef struct { 
    uint64_t low, high; 
} uint128;

（除非你能指點一個快速128bit的整數庫我不能改變的）

現在我想使用printf以10爲基數打印這樣一個值。我可能需要10分來做到這一點，但是還沒有實施分工。

我該怎麼做？只要有效，解決方案不一定非常高效。

編輯：我喜歡你想出的所有解決方案。你太棒了。

來源

2010-12-05 Cephalopod

你在什麼操作系統上？例如，Solaris有一個內置的大整數庫。你也可以谷歌BIGNUM庫。 – 2010-12-05 22:26:01

GCC 4.6.0將有[__int128]（http://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html）。 – ephemient 2010-12-05 22:30:40

我更喜歡獨立於平臺和編譯器的解決方案。 – Cephalopod 2010-12-06 10:06:36

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-06 08:10:49

如果您不想爲128位值實施除法，您可以預先計算代表10的冪的幾個（〜40）128位值，並使用減法。

實際上只有更高的qword以這種方式進行處理，因爲對於較低的部分，您可以使用printf("%I64d")。

編輯：這裏有一個例子（它會打印只用算術一個short上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-05 22:25:05 ruslik

假設您已經實現了在uint128上執行數學運算的功能，您可以將數字分成3部分並使用內置的64位printf的打印功能gest 64位數字的長度是20位數，這意味着所有19位十進制數字都可以這樣打印，但由於最大的128位數字是39位數字，所以我們不能將它分成只有2個部分，因爲我們有可能會得到比最大的64位數大20位數的數字。

這裏有一種方法，首先除以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); 
}

來源

2010-12-05 22:48:01

您可以用乘法來打印數量。

作爲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：對於一位數字需要專用的步驟是合理的，因爲如果將其旁邊的數字相乘，則應該得到一個溢出，如果餘數大於34E36。

來源

2010-12-06 09:21:37 Vovanium

C：在基地打印的BigInteger 10

回答

相關問題