Come convertire un intero a 128 bit in una stringa ascii decimale in C?

Question

Sto cercando di convertire un intero senza segno a 128 bit memorizzato come una matrice di 4 unsigned int alla rappresentazione della stringa decimale in C:

unsigned int src[] = { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 }; 
printf("%s", some_func(src)); // gives "53072739890371098123344" 

(Gli esempi di ingresso e uscita sopra sono completamente inventati; ho nessuna idea di cosa produrrebbe quell'input.)

Se stavo andando in esadecimale, binario o ottale, questa sarebbe una semplice questione di maschere e bit shift per rimuovere i caratteri meno significativi. Tuttavia, mi sembra che ho bisogno di fare la divisione base 10. Sfortunatamente, non riesco a ricordare come farlo attraverso più int e il sistema che sto usando non supporta tipi di dati maggiori di 32-bit, quindi non è possibile usare un tipo a 128-bit. Usando una lingua diversa è anche fuori, e preferirei evitare una grande libreria di numeri solo per questa operazione.

Answer 1

divisione non è necessaria:

#include <string.h> 
#include <stdio.h> 

typedef unsigned long uint32; 

/* N[0] - contains least significant bits, N[3] - most significant */ 
char* Bin128ToDec(const uint32 N[4]) 
{ 
    // log10(x) = log2(x)/log2(10) ~= log2(x)/3.322 
    static char s[128/3 + 1 + 1]; 
    uint32 n[4]; 
    char* p = s; 
    int i; 

    memset(s, '0', sizeof(s) - 1); 
    s[sizeof(s) - 1] = '\0'; 

    memcpy(n, N, sizeof(n)); 

    for (i = 0; i < 128; i++) 
    { 
    int j, carry; 

    carry = (n[3] >= 0x80000000); 
    // Shift n[] left, doubling it 
    n[3] = ((n[3] << 1) & 0xFFFFFFFF) + (n[2] >= 0x80000000); 
    n[2] = ((n[2] << 1) & 0xFFFFFFFF) + (n[1] >= 0x80000000); 
    n[1] = ((n[1] << 1) & 0xFFFFFFFF) + (n[0] >= 0x80000000); 
    n[0] = ((n[0] << 1) & 0xFFFFFFFF); 

    // Add s[] to itself in decimal, doubling it 
    for (j = sizeof(s) - 2; j >= 0; j--) 
    { 
     s[j] += s[j] - '0' + carry; 

     carry = (s[j] > '9'); 

     if (carry) 
     { 
     s[j] -= 10; 
     } 
    } 
    } 

    while ((p[0] == '0') && (p < &s[sizeof(s) - 2])) 
    { 
    p++; 
    } 

    return p; 
} 

int main(void) 
{ 
    static const uint32 testData[][4] = 
    { 
    { 0, 0, 0, 0 }, 
    { 1048576, 0, 0, 0 }, 
    { 0xFFFFFFFF, 0, 0, 0 }, 
    { 0, 1, 0, 0 }, 
    { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 } 
    }; 
    printf("%s\n", Bin128ToDec(testData[0])); 
    printf("%s\n", Bin128ToDec(testData[1])); 
    printf("%s\n", Bin128ToDec(testData[2])); 
    printf("%s\n", Bin128ToDec(testData[3])); 
    printf("%s\n", Bin128ToDec(testData[4])); 
    return 0; 
} 

uscita:

0 
1048576 
4294967295 
4294967296 
11248221411398543556294285637029484152 

Answer 2

In realtà non è necessario implementare la divisione lunga. È necessario implementare la moltiplicazione con una potenza di due e aggiunta. Hai quattro uint_32. Prima converti ciascuno di essi in una stringa. Moltiplicali per (2^32)^3, (2^32)^2, (2^32)^1 e (2^32)^0 rispettivamente, quindi aggiungili insieme. Non è necessario eseguire la conversione di base, è sufficiente gestire i quattro pezzi. Ovviamente dovrai assicurarti che le stringhe possano gestire un numero fino a UINT_32_MAX*(2^32)^3.

Answer 3

Un approccio lento ma semplice consiste semplicemente nella stampa di cifre dal più significativo al meno significativo utilizzando la sottrazione. Fondamentalmente è necessaria una funzione per verificare se x >= y e un altro per il calcolo x -= y quando questo è il caso. Quindi puoi iniziare a contare quante volte puoi sottrarre 10^38 (e questa sarà la cifra più significativa), quindi quante volte puoi sottrarre 10^37 ... giù a quante volte puoi sottrarre 1.

la seguente è una piena attuazione di questo approccio:

#include <stdio.h> 

typedef unsigned ui128[4]; 

int ge128(ui128 a, ui128 b) 
{ 
    int i = 3; 
    while (i >= 0 && a[i] == b[i]) 
     --i; 
    return i < 0 ? 1 : a[i] >= b[i]; 
} 

void sub128(ui128 a, ui128 b) 
{ 
    int i = 0; 
    int borrow = 0; 
    while (i < 4) 
    { 
     int next_borrow = (borrow && a[i] <= b[i]) || (!borrow && a[i] < b[i]); 
     a[i] -= b[i] + borrow; 
     borrow = next_borrow; 
     i += 1; 
    } 
} 

ui128 deci128[] = {{1u,0u,0u,0u}, 
        {10u,0u,0u,0u}, 
        {100u,0u,0u,0u}, 
        {1000u,0u,0u,0u}, 
        {10000u,0u,0u,0u}, 
        {100000u,0u,0u,0u}, 
        {1000000u,0u,0u,0u}, 
        {10000000u,0u,0u,0u}, 
        {100000000u,0u,0u,0u}, 
        {1000000000u,0u,0u,0u}, 
        {1410065408u,2u,0u,0u}, 
        {1215752192u,23u,0u,0u}, 
        {3567587328u,232u,0u,0u}, 
        {1316134912u,2328u,0u,0u}, 
        {276447232u,23283u,0u,0u}, 
        {2764472320u,232830u,0u,0u}, 
        {1874919424u,2328306u,0u,0u}, 
        {1569325056u,23283064u,0u,0u}, 
        {2808348672u,232830643u,0u,0u}, 
        {2313682944u,2328306436u,0u,0u}, 
        {1661992960u,1808227885u,5u,0u}, 
        {3735027712u,902409669u,54u,0u}, 
        {2990538752u,434162106u,542u,0u}, 
        {4135583744u,46653770u,5421u,0u}, 
        {2701131776u,466537709u,54210u,0u}, 
        {1241513984u,370409800u,542101u,0u}, 
        {3825205248u,3704098002u,5421010u,0u}, 
        {3892314112u,2681241660u,54210108u,0u}, 
        {268435456u,1042612833u,542101086u,0u}, 
        {2684354560u,1836193738u,1126043566u,1u}, 
        {1073741824u,1182068202u,2670501072u,12u}, 
        {2147483648u,3230747430u,935206946u,126u}, 
        {0u,2242703233u,762134875u,1262u}, 
        {0u,952195850u,3326381459u,12621u}, 
        {0u,932023908u,3199043520u,126217u}, 
        {0u,730304488u,1925664130u,1262177u}, 
        {0u,3008077584u,2076772117u,12621774u}, 
        {0u,16004768u,3587851993u,126217744u}, 
        {0u,160047680u,1518781562u,1262177448u}}; 

void print128(ui128 x) 
{ 
    int i = 38; 
    int z = 0; 
    while (i >= 0) 
    { 
     int c = 0; 
     while (ge128(x, deci128[i])) 
     { 
      c++; sub128(x, deci128[i]); 
     } 
     if (i==0 || z || c > 0) 
     { 
      z = 1; putchar('0' + c); 
     } 
     --i; 
    } 
} 

int main(int argc, const char *argv[]) 
{ 
    ui128 test = { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 }; 
    print128(test); 
    return 0; 
} 

Quel numero nel testo problema in decimale diventa

11248221411398543556294285637029484152 

e Python è d'accordo questo è il valore corretto (questo naturalmente non lo fa significa che il codice è corretto !!! ;-))

Answer 4

Semplice base di divisione 2^32, stampe cifre decimali in ordine inverso, utilizza 64 bit aritmetica, complessità O(n) dove n è il numero di cifre decimali nella rappresentazione:

#include <stdio.h> 

unsigned int a [] = { 0x12345678, 0x12345678, 0x12345678, 0x12345678 }; 

/* 24197857161011715162171839636988778104 */ 

int 
main() 
{ 
    unsigned long long d, r; 

    do 
    { 
     r = a [0]; 

     d = r/10; 
     r = ((r - d * 10) << 32) + a [1]; 
     a [0] = d; 

     d = r/10; 
     r = ((r - d * 10) << 32) + a [2]; 
     a [1] = d; 

     d = r/10; 
     r = ((r - d * 10) << 32) + a [3]; 
     a [2] = d; 

     d = r/10; 
     r = r - d * 10; 
     a [3] = d; 

     printf ("%d\n", (unsigned int) r); 
    } 
    while (a[0] || a[1] || a[2] || a[3]); 

    return 0; 
} 

MODIFICA: corretto il ciclo in modo che venga visualizzato un numero 0 se l'array a contiene solo zeri. Inoltre, la matrice viene letta da sinistra a destra, una [0] è la più significativa, una [3] è una cifra meno significativa.

Answer 5

Stessa cosa, ma con 32 bit aritmetica intera:

#include <stdio.h> 

unsigned short a [] = { 
    0x0876, 0x5421, 
    0xfedc, 0xba90, 
    0x90ab, 0xcdef, 
    0x1234, 0x5678 
}; 

int 
main() 
{ 
    unsigned int d, r; 

    do 
    { 
     r = a [0]; 

     d = r/10; 
     r = ((r - d * 10) << 16) + a [1]; 
     a [0] = d; 

     d = r/10; 
     r = ((r - d * 10) << 16) + a [2]; 
     a [1] = d; 

     d = r/10; 
     r = ((r - d * 10) << 16) + a [3]; 
     a [2] = d; 

     d = r/10; 
     r = ((r - d * 10) << 16) + a [4]; 
     a [3] = d; 

     d = r/10; 
     r = ((r - d * 10) << 16) + a [5]; 
     a [4] = d; 

     d = r/10; 
     r = ((r - d * 10) << 16) + a [6]; 
     a [5] = d; 

     d = r/10; 
     r = ((r - d * 10) << 16) + a [7]; 
     a [6] = d; 

     d = r/10; 
     r = r - d * 10; 
     a [7] = d; 

     printf ("%d\n", r); 
    } 
    while (a[0] || a[1] || a[2] || a[3] || a [4] || a [5] || a[6] || a[7]); 


    return 0; 
} 

Answer 6

Supponendo di avere un facile 32 bit moltiplicazione e divisione il risultato può essere calcolata 4 cifre alla volta attuando una divisione bigint/modulo 10000 e quindi usando (s) printf per l'output di gruppi di cifre.

Questo approccio è anche banale estendere ad una maggiore precisione (o variabile) ...

#include <stdio.h> 

typedef unsigned long bigint[4]; 

void print_bigint(bigint src) 
{ 
    unsigned long int x[8]; // expanded version (16 bit per element) 
    int result[12];   // 4 digits per element 
    int done = 0;    // did we finish? 
    int i = 0;    // digit group counter 

    /* expand to 16-bit per element */ 
    x[0] = src[0] & 65535; 
    x[1] = src[0] >> 16; 
    x[2] = src[1] & 65535; 
    x[3] = src[1] >> 16; 
    x[4] = src[2] & 65535; 
    x[5] = src[2] >> 16; 
    x[6] = src[3] & 65535; 
    x[7] = src[3] >> 16; 

    while (!done) 
    { 
     done = 1; 
     { 
      unsigned long carry = 0; 
      int j; 
      for (j=7; j>=0; j--) 
      { 
       unsigned long d = (carry << 16) + x[j]; 
       x[j] = d/10000; 
       carry = d - x[j] * 10000; 
       if (x[j]) done = 0; 
      } 
      result[i++] = carry; 
     } 
    } 

    printf ("%i", result[--i]); 
    while (i > 0) 
    { 
     printf("%04i", result[--i]); 
    } 
} 

int main(int argc, const char *argv[]) 
{ 
    bigint tests[] = { { 0, 0, 0, 0 }, 
         { 0xFFFFFFFFUL, 0, 0, 0 }, 
         { 0, 1, 0, 0 }, 
         { 0x12345678UL, 0x90abcdefUL, 0xfedcba90UL, 0x8765421UL } }; 
    { 
     int i; 
     for (i=0; i<4; i++) 
     { 
      print_bigint(tests[i]); 
      printf("\n"); 
     } 
    } 
    return 0; 
} 

Answer 7

metodo @Alexey Frunze è facile ma è molto lento. Dovresti utilizzare il metodo integer a 32 bit di @ chill qui sopra. Un altro metodo facile senza alcuna moltiplicazione o divisione è double dabble. Questo potrebbe funzionare più lentamente dell'algoritmo di chill ma molto più veloce di quello di Alexey. Dopo aver eseguito, avrai un numero BCD del numero decimale compresso