Come posso tranquillamente media due unsigned int in C ++?
-
26-09-2019 - |
Domanda
Utilizzando intero matematica da sola, mi piacerebbe "in sicurezza" media due unsigned int in C ++.
cosa intendo per overflow "in sicurezza" è di evitare (e qualsiasi altra cosa che può essere pensato).
Per esempio, la media 200 e 5000 è facile:
unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended
Ma nel caso di 4294967295 e 5000 quindi:
unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147
Il migliore che è venuta in mente è:
unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected
sono modi migliori lì?
Soluzione
La tua ultima approccio sembra promettente. Si può migliorare su questo considerando manualmente i bit più bassi di A e B:
unsigned int average = (a / 2) + (b / 2) + (a & b & 1);
In questo modo i risultati corretti in caso sia a che b sono dispari.
Altri suggerimenti
unsigned int average = low + ((high - low) / 2);
Modifica
Ecco un articolo correlato: http : //googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Il metodo non è corretto se entrambi i numeri dispari sono ad esempio 5 e 7, la media è di 6, ma i tuoi Metodo # 3 restituisce 5.
Prova questo:
average = (a>>1) + (b>>1) + (a & b & 1)
con gli operatori matematici solo:
average = a/2 + b/2 + (a%2) * (b%2)
Se non ti dispiace un po 'x86 linea di assemblaggio (GNU C sintassi), è possibile usufruire di suggestione di Supercat ad uso rotate-con-carry dopo un add mettere le alte 32 bit del risultato pieno 33 bit in un registro
Naturalmente, è di solito dovrebbe mente usando inline-asm, perché sconfigge alcune ottimizzazioni ( https://gcc.gnu.org/wiki/DontUseInlineAsm ). Ma qui andiamo in ogni caso:
// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
unsigned result;
asm("add %[x], %[res]\n\t"
"rcr %[res]"
: [res] "=r" (result) // output
: [y] "%0"(y), // input: in the same reg as results output. Commutative with next operand
[x] "rme"(x) // input: reg, mem, or immediate
: // no clobbers. ("cc" is implicit on x86)
);
return result;
}
Il %
modificatore per dire al compilatore i args sono commutativa non effettivamente contribuire a rendere meglio asm nel caso ho provato, chiamando la funzione con y con una costante o puntatore deref (memoria operando). Probabilmente con un vincolo di corrispondenza per un'uscita operando sconfitte che, poiché non è possibile utilizzarlo con operandi di lettura-scrittura.
Come si può vedere sul Godbolt compilatore esploratore , questo compilato correttamente, e così fa una versione in cui cambiamo gli operandi per unsigned long
, con la stessa asm inline. clang3.9 fa un pasticcio di esso, però, e decide di utilizzare l'opzione "m"
per il vincolo "rme"
, quindi memorizza alla memoria e utilizza una memoria operando.
RCR-by-one non è troppo lento, ma è ancora 3 UOP su Skylake, con latenza 2 ciclo. E 'great su AMD CPU, dove RCR ha latenza ciclo unico. (Fonte: tavoli istruzione Agner di nebbia , puoi anche consultare la x86 tag wiki per i collegamenti di performance x86). E 'sempre meglio di @ versione sellibitze, ma peggio di @ versione fine-dipendente di Sheldon. (Vedi codice su Godbolt)
Ma ricordate che sconfigge inline-ASM ottimizzazioni come costante di propagazione, in modo versione qualsiasi puro-C ++ sarà meglio in questo caso.
E la risposta corretta è ...
(A&B)+((A^B)>>1)
Quello che hai va bene, con il piccolo dettaglio che possa affermare che la media di 3 e 3 è 2. Sto indovinando che non vuoi che; Fortunatamente, c'è una soluzione semplice:
unsigned int average = a/2 + b/2 + (a & b & 1);
Questo urta solo la parte posteriore media nel caso in cui entrambe le divisioni sono stati troncati.
Se il codice è per un micro incorporato e se la velocità è un fattore critico, assemblaggio lingua può essere utile. Su molti microcontrollori, il risultato del componente aggiuntivo sarebbe naturalmente andare in carry flag, e le istruzioni esistere a spostare di nuovo in un registro. Su un braccio, l'operazione di media (sorgente e dest nei registri.) Potrebbe essere fatto in due istruzioni; qualsiasi equivalente linguaggio C sarebbe probabilmente resa di almeno 5, e probabilmente un bel po 'di più.
Per inciso, su macchine con dimensioni parola più corta, le differenze possono essere ancora più consistente. Su un 8-bit PIC-18 della serie, con una media di due numeri a 32 bit avrebbe preso dodici istruzioni. Fare la turni, add, e la correzione, avrebbe preso 5 istruzioni per ogni turno, otto per l'add, e otto per la correzione, quindi 26 (non proprio una differenza 2.5x, ma probabilmente più significativo in termini assoluti).
(((a&b << 1) + (a^b)) >> 1)
è anche un bel modo.
Per gentile concessione: http://www.ragestorm.net/blogs/?p=29
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
decimal avg = 0;
for (int i = 0; i < array.Length; i++){
avg = (array[i] - avg) / (i+1) + avg;
}
si aspetta avg == 5.0 per questo test