我使用這個結構來表示128bit的整數:C:在基地打印的BigInteger 10
typedef struct {
uint64_t low, high;
} uint128;
(除非你能指點一個快速128bit的整數庫我不能改變的)
現在我想使用printf
以10爲基數打印這樣一個值。我可能需要10分來做到這一點,但是還沒有實施分工。
我該怎麼做?只要有效,解決方案不一定非常高效。
編輯:我喜歡你想出的所有解決方案。你太棒了。
我使用這個結構來表示128bit的整數:C:在基地打印的BigInteger 10
typedef struct {
uint64_t low, high;
} uint128;
(除非你能指點一個快速128bit的整數庫我不能改變的)
現在我想使用printf
以10爲基數打印這樣一個值。我可能需要10分來做到這一點,但是還沒有實施分工。
我該怎麼做?只要有效,解決方案不一定非常高效。
編輯:我喜歡你想出的所有解決方案。你太棒了。
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]);
}
如果您不想爲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
範圍內
假設您已經實現了在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);
}
您可以用乘法來打印數量。
作爲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。
你在什麼操作系統上?例如,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