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ビット値の除算を実装したくない場合は、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-05T22:25:05.607 に答える
2

で数学を実行する関数をすでに実装していると仮定すると、数値uint128を3つの部分に分割して、printfの組み込みの64ビット印刷機能を使用できます。最大の64ビットの数値は20桁の長さであるため、19桁の10進数はすべてそのように印刷できますが、最大の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);
}
于 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より大きい場合、その隣の数値を乗算するとオーバーフローが発生するため、1桁目の専用ステップの必要性はjusです。

于 2010-12-06T09:21:37.907 に答える