C: Reprezentacja dużych liczb całkowitych

Question

Załóżmy, że utworzyłem strukturę 3 32-bitowych liczb całkowitych, które działają jako 96-bitowa liczba całkowita.

typedef struct { 
    unsigned int x, y, z; 
} Int96; 

Załóżmy, że int x jest pierwszą liczbą całkowitą do wypełnienia. Zanim przepełni się, y jest inkrementowane, a x jest odświeżany z powrotem do funkcji 0. z podobnie, ale dba o przepełnienie y.

Jak mógłbym wydrukować wartość przechowywaną w tej strukturze? Z pewnością nie mogę bezpośrednio wydrukować pełnej wartości bez powodowania przekroczenia mojego systemu.

Answer 1

Pierwszym krokiem jest napisanie ogólnego zastosowania arytmetycznych procedur dla Int96:

void Add96(Int96 *a, const Int96 *b) { 
    // add b to a 
    a->x += b->x; 
    a->y += b->y; 
    a->z += b->z; 
    if (a->y < b->y) a->z++; 
    if (a->x < b->x && ++a->y == 0) a->z++; } 
void Sub96(Int96 *a, const Int96 *b); 
void Mul96(Int96 *a, const Int96 *b); 
void Div96(Int96 *a, const Int96 *b); 
void Mod96(Int96 *a, const Int96 *b); 

z tymi, można napisać:

void print96(const Int96 *val) { 
    Int96 ten = { 10, 0, 0 }; 
    Int96 div = *val; 
    Int96 mod = *val; 
    Div96(&div, &ten); 
    Mod96(&mod, &ten); 
    if (div.x || div.y || div.z) print96(&div); 
    putchar('0' + mod.x); } 

Można uczynić to bardziej efektywne pisząc DivMod96uint funkcję, która robi div i mod w jednym kroku i pobierają unsigned (zamiast Int96) dla drugiego argumentu i zwracają mod. Można również uniknąć dodatkową kopię za cyfrą przez posiadające print96destructive funkcję, która nadpisuje swój argument i mają print96 prostu zrobić kopię, a następnie zadzwonić, że:

void print96destructive(Int96 *val) { 
    unsigned mod = DivMod96ui(val, 10); 
    if (val->x || val->y || val->z) print96destructive(val); 
    putchar('0' + mod); } 
void print96(const Int96 *val) { 
    Int96 v = *val; 
    print96destructive(&v); } 

unsigned DivMod96ui(Int96 *a, unsigned b) { 
    unsigned mod = a->z % b; 
    a->z /= b; 
    uint64_t y = a->y + ((uint64_t)mod << 32); 
    mod = y % b; 
    a->y = y/b; 
    uint64_t x = a->x + ((uint64_t)mod << 32); 
    mod = x % b; 
    a->x = x/b; 
    return mod; }