Come posso tranquillamente media due unsigned int in C ++?

StackOverflow https://stackoverflow.com/questions/3816446

  •  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ì?

È stato utile?

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 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

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top