Il modo migliore per ottenere le singole cifre da int per l'ordinamento digitale in C/C++

Question

Qual è il modo migliore per ottenere cifre individuali da un numero intero con numero di cifre da utilizzare in un algoritmo di ordinamento digitale? Mi chiedo se c'è un modo particolarmente valido per farlo in C/C++, se no qual è la soluzione migliore generale?

modifica: solo per chiarire, stavo cercando una soluzione diversa dalla conversione in una stringa e trattandola come una serie di cifre.

Answer 1

Utilizzare le cifre della dimensione 2^k. Per estrarre il n -esima cifra:

#define BASE (2<<k) 
#define MASK (BASE-1) 

inline unsigned get_digit(unsigned word, int n) { 
    return (word >> (n*k)) & MASK; 
} 

usando lo spostamento e la maschera (abilitato da base essendo una potenza di 2) evita costosi istruzioni interi divide.

Dopodiché, la scelta della base migliore è una domanda sperimentale (intervallo tempo/spazio per il tuo particolare hardware). Probabilmente k==3 (base 8) funziona bene e limita il numero di bucket, ma k==4 (base 16) sembra più attraente perché divide la dimensione della parola. Tuttavia, non c'è davvero nulla di sbagliato in una base che non divida la dimensione della parola, e potresti trovare che la base 32 o la base 64 hanno prestazioni migliori. È una domanda sperimentale e potrebbe differire in base all'hardware, a seconda di come si comporta la cache e di quanti elementi ci sono nell'array.

Nota finale: se si ordina con segno numeri interi, la vita è un dolore molto più grande, perché si desidera trattare il bit più significativo come firmato. Ti consiglio di considerare tutto come non firmato, e se davvero hai bisogno di firmare, nell'ultimo passaggio del tuo ordinamento digitale cambierai i bucket, in modo che i bucket con uno più significativo 1 arrivino prima di uno più significativo 0. Questo problema è sicuramente più facile se k divide la dimensione della parola.

Answer 2

Non utilizzare base 10, uso base 16.

for (int i = 0; i < 8; i++) { 
    printf("%d\n", (n >> (i*4)) & 0xf); 
} 

Poiché interi sono memorizzati internamente in binario, questo sarà più efficiente rispetto dividere per 10 per determinare decimali cifre.