Come determinare i tipi interi che hanno il doppio della larghezza di `int` e` unsigned`?

I valori di moltiplicazione intermedia in genere richiedono il doppio del numero di bit come input.

// Example int foo(int a, int b, int carry, int rem) { int2x c; // Some type that is twice as wide at `int` c = (int2x)a * b + carry; return (int) (c % rem); } 

Considerando il potenziale per il riempimento, (che sembra limitare l’utilità sizeof() ) e gli interi del complemento di non-2 (che limita il bit dibbling), …

Il seguente crea sempre il tipo necessario?
In caso negativo, come codificare almeno una soluzione ragionevole, anche se non del tutto portatile?


 #include  #include  #if LONG_MAX/2/INT_MAX - 2 == INT_MAX typedef long int2x; typedef unsigned long unsigned2x; #elif LLONG_MAX/2/INT_MAX - 2 == INT_MAX typedef long long int2x; typedef unsigned long long unsigned2x; #elif INTMAX_MAX/2/INT_MAX - 2 == INT_MAX typedef intmax_t int2x; typedef uintmax_t unsigned2x; #else #error int2x/unsigned2x not available #endif 

[Modificare]
Qualifica: “sempre”, se long , long long e intmax_t , non funziona, va bene a #error .
Quello che voglio sapere è se almeno 1 di long , long long o intmax_t funzionerà, int2x sarà digitato correttamente?

Note: Quanto sopra presuppone che xxx_MAX sia un po ‘dispari di potenza-di-meno 1. Forse una buona ipotesi? Quanto sopra funziona su almeno 2 piattaforms, ma non è certo un grande test di portabilità.

L’ipotesi che tutte le costanti * _MAX siano nella forma (2^n)-1 è valida. Vedere 6.2.6 Rappresentazioni di Tipi e in particolare 6.2.6.2 Tipi interi , in cui le rappresentazioni di tipi interi senza segno e i valori positivi dei tipi interi con segno sono completamente definiti come puro binario, ottenendo così un massimo che è uno in meno di un potere di Due.

Per i tipi signed è meglio lavorare solo con l’ intervallo di valori dei tipi considerati e confrontarli.

In primo luogo, si proverebbe a calcolare INT_MAX*INTMAX+INT_MAX per avere il massimo valore ansible nell’espressione a*b+carry . intmax_t a intmax_t sembra l’approccio più ragionevole:

  #define MAX_EXPRESSION ((intmax_t) INT_MAX * INTMAX + INT_MAX) 

Tuttavia, possiamo cadere nei guai se il vero valore matematico di MAX_EXPRESSION è maggiore di INTMAX_MAX . Quindi, facciamo un po ‘di matematica per risolvere questo problema.

Indichiamo c = INT_MAX e m = INTMAX_MAX . Vogliamo sapere se c*c+c <= m , matematicamente parlando. Questo ci porta alla disequazione: c <= (m - c) / c . Poiché la divisione è intera, il risultato viene troncato, quindi i calcoli matematici esatti vengono persi nell'ultima operazione. Quindi, dobbiamo scrivere un'espressione più precisa, come questa: `c <= floor ((m - c) / c) + fractional_part_of ((m - c) / c).

Se c > floor((m - c) / c) , rigorosamente, quindi c >= floor((m - c) / c) + 1 > (m - c) / c , dove la divisione è presa in senso matematico ( con decimali esatti). che ci dà c*c+c > m , contraddizione. Quindi, concludiamo che c <= floor((m - c) / c) , di nuovo, matematicamente parlando.

Questa espressione è più comoda in C , perché m - c ci darà un valore corretto quando calcasting con il tipo intmax_t (in altre parole: non è un valore fuori intervallo ). Ora, la divisione (m - c) / c ci darà un numero intero nell'intervallo di intmax_t , di nuovo, benché possibilmente troncato, perché la divisione è intera. In realtà, ci dà il valore floor((m - c) / c , senza esitazione.

Questo confronto dà il vero, quindi possiamo dire che c*c+c è rappresentabile nel più grande tipo intero con segno del tuo sistema, cioè intmax_t . In particolare: esiste un tipo di intero con segno che è in grado di rappresentare il valore c*c+c nel sistema.

Ora, nel codice C , possiamo scrivere:

  #define c INT_MAX #define m INTMAX_MAX #if (c <= (m - c) / c) // There exists a signed type in your system // such that INT_MAX*INTMAX+INT_MAX is representable // as a value in that type. #else #error Sorry, the size of INT_MAX cannot be doubled... #endif 

Una volta determinato che intmax_t fa il lavoro, puoi semplicemente avviare una ricerca per il tipo di intero con intmax_t con una classificazione minima che risolva il problema: possiamo chiedere ancora la stessa domanda che abbiamo fatto per intmax_t , ad esempio per long e long long :

  #include  #include  #define c INT_MAX #if (c <= (INTMAX_MAX - c) / c) #if (c <= (LLONG_MAX - c) / c) #if (c <= (LONG_MAX - c) / c) typedef long int2x; #else typedef long long int2x; #endif #else typedef intmax_t int2x; #endif #else #error Sorry, the size of type "int" cannot be doubled... #endif