C：ベース10にBigintegerを印刷します

StackOverflow https://stackoverflow.com/questions/4361441

質問

私はこの構造を使用して128bit整数を表しています。

typedef struct {
    uint64_t low, high;
} uint128;

（高速な128ビット整数ライブラリを私に向けることができない限り、私はそれを変更することはできません）

今、私はベース10にそのような値を印刷したいと思います。 printf. 。おそらくそれを行うには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の少数の事前計算されたパワーを使用できますが、それはそれを遅くします（ex、それらを100のステップに置いてください。 ctr 範囲内にあること 0..99.

数学を実行する機能を既に実装していると仮定します uint128, 、数字を3つの部分に分割し、PrintFの組み込み64ビット印刷機能を使用できます。最大の64ビット数は20桁の長さであるため、19桁の小数点すべてをそのように印刷できることを意味しますが、最大128ビット数は39桁であるため、2部のみに分割することはできません。 、最大の64ビット数よりも大きい20桁の数になる可能性があるからです。

これがそれを行う1つの方法です、最初に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);
}

乗算を使用して番号を印刷できます。

  1. として2128 100E36、200E36、および300E36の境界と数を比較することにより、最初に先行桁を決定します。数字を書き、最も少ない境界を差し引きます。 E. g。数字が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：1秒の桁の専用ステップの必要性はjusです。なぜなら、その隣の数値を掛けている場合、残りが34E36を超える場合、オーバーフローが得られるはずです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top