Identifica numeri dispari, pari - binario vs. mod

Question

Recentemente ho dovuto identificare se un numero è pari o dispari per un numero elevato di numeri interi. Ho pensato di un'idea di identificare un numero come pari o dispari da AND-ing contro 1 e confrontando il risultato di 1

x & 1 == 1 // even or odd 

Non ho mai visto questa implementazione nella pratica. Il modo più comune si vedono sempre è:

x % 2 == 0 

ho deciso di fare un po 'di controllo delle prestazioni su entrambi i metodi e il metodo binario sembra leggermente più veloce sulla mia macchina.

int size = 60000000; 
List<int> numberList = new List<int>(); 
Random rnd = new Random(); 

for (int index = 0; index < size; index++) 
{ 
    numberList.Add(rnd.Next(size)); 
} 

DateTime start; 
bool even; 

// regular mod 
start = DateTime.Now; 
for (int index = 0; index < size; index++) 
{ 
    even = (numberList[index] % 2 == 0); 
} 
Console.WriteLine("Regualr mod : {0}", DateTime.Now.Subtract(start).Ticks); 

// binary 
start = DateTime.Now; 
for (int index = 0; index < size; index++) 
{ 
    even = ((numberList[index] & 1) != 1); 
} 
Console.WriteLine("Binary operation: {0}", DateTime.Now.Subtract(start).Ticks); 

Console.ReadKey(); 

Qualcuno ha visto il metodo binario implementato? Qualche inconveniente?

Answer 1

Beh, sì, si tratta di una leggera ottimizzazione. Questo frammento di codice:

 uint ix = 3; // uint.Parse(Console.ReadLine()); 
     bool even = ix % 2 == 0; 

genera questo codice macchina nella build di rilascio:

  uint ix = 3; 
0000003c mov   dword ptr [ebp-40h],3 
      bool even = ix % 2 == 0; 
00000043 mov   eax,dword ptr [ebp-40h] 
00000046 and   eax,1 
00000049 test  eax,eax 
0000004b sete  al 
0000004e movzx  eax,al 
00000051 mov   dword ptr [ebp-44h],eax 

si noti che il compilatore JIT è abbastanza intelligente per utilizzare l'istruzione AND processore. Non sta facendo una divisione come l'operatore% normalmente eseguirà. Complimenti lì.

Ma il test personalizzato genera questo codice:

 uint ix = uint.Parse(Console.ReadLine()); 
// Bunch of machine code 
     bool even = (ix & 1) == 0; 
00000024 test  eax,1 
00000029 sete  al 
0000002c movzx  eax,al 
0000002f mov   esi,eax 

ho dovuto modificare l'istruzione di assegnazione perché il compilatore JIT ha improvvisamente intelligente e ha valutato l'espressione in fase di compilazione. Il codice è molto simile a ma l'istruzione AND è stata sostituita da un'istruzione TEST. Salvare una istruzione nel processo. Abbastanza ironico come questa volta ha scelto di non utilizzare un AND :)

Queste sono le trappole di fare ipotesi. Il tuo istinto originale aveva ragione, tuttavia, dovrebbe risparmiare circa mezzo nanosecondo. Very difficile vedere quello indietro a meno che questo codice non risulti in un ciclo molto stretto. Diventa drasticamente diverso quando si cambia la variabile da uint a int, il compilatore JIT genera quindi codice che cerca di essere intelligente riguardo al bit del segno. Inutilmente.

Answer 2

Il metodo binario non sarebbe più veloce perché il compilatore è in grado di ottimizzare questo in un bithift piuttosto che forzare la cpu a eseguire il calcolo della divisione?

Answer 3

Per tali operazioni si dovrebbe preferire l'approccio più leggibile (a mio parere il modulo-via) rispetto a quello che si pensa sia più veloce.

Inoltre, l'operazione modulo sopra può essere ottimizzata dal compilatore in bitwise e operazione. Pertanto, in realtà non è necessario preoccuparsi.

Nota per l'esempio: per ottenere risultati più precisi, prendere in considerazione il superamento del numero di elementi da aggiungere al costruttore della lista. In tal modo si evitano le discrepanze introdotte dalla riallocazione multipla dell'array di supporto. Per 60 milioni di elementi interi (circa 240 MB di memoria) la non preallocazione della memoria può rappresentare un pregiudizio significativo.

Answer 4

Sono d'accordo con le altre risposte, che dovresti utilizzare il controllo modulo, perché trasmette al meglio l'intento.

Tuttavia, per i risultati specifici; prova a utilizzare la variabile even. Farà una differenza significativa, perché il compilatore potrebbe effettivamente ottimizzare alcuni calcoli perché sa che non avrà bisogno di usare il valore.

Utilizzando il programma (modificato per utilizzare il cronometro), ottengo 70 ms per la mod normale e 88 ms per l'operazione binaria. Se utilizzo la variabile even, la differenza è molto più piccola (327 vs 316 ms) e il modulo è il più veloce.

Answer 5

Bitwise e batterà la divisione modulo ogni giorno della settimana. La divisione per un numero arbitrario richiede un sacco di cicli di clock, mentre bitwise ed è un op primitivo essenziale che quasi sempre si completa in un ciclo di clock, indipendentemente dall'architettura della CPU.

Quello che si sta vedendo, tuttavia, è che il compilatore potrebbe sostituire x mod 2 con un'istruzione bit shift o bit mask che avrà prestazioni identiche alla propria operazione di bit mask.

Per confermare che il compilatore sta giocando brutti scherzi con il tuo codice, confronta le prestazioni di x mod 2 con x mod 7 o qualsiasi altro non base 2 intero.O oscuro operandi dal compilatore in modo che non può eseguire l'ottimizzazione:

var y = 2; 
result = x mod y; 

Se si vede una differenza drammatica in tempo di esecuzione con questi cambiamenti, allora questo è un piuttosto forte indicatore che il compilatore sta trattando x mod 2 come un caso speciale e non utilizzare la divisione effettiva per trovare il resto.

E se si utilizza DateTime per eseguire operazioni di benchmark su istruzione singola, assicurarsi di disporre di un ciclo sufficientemente lungo da eseguire il test per almeno 5 minuti in modo da ottenere una misura reale al di sopra della soglia del rumore.

Answer 6

Per i numeri non firmati, molti compilatori ottimizzeranno l'operatore 'mod' come un 'e' test. Per i numeri firmati, (x% 2) sarà 1 se il numero è dispari e positivi; -1 se è dispari e negativi; anche se entrambi +1 e -1 non sono zero, potrebbero non essere riconosciuti come equivalenti.

BTW, quando si utilizza l'operatore "and", vorrei testare per! = 0 anziché == 1. I compilatori possono riconoscere l'equivalenza, ma non possono.

Answer 7

This webpage benchmark almeno una mezza dozzina di modi per determinare se un numero è pari o dispari.

Il più veloce è stato (che mi piace per una migliore leggibilità):

if (x % 2 == 0) 
    //even number 
else 
    //odd number 

Qui sono stati testati altri (code is here). In realtà sto sorpreso il bit per bit e morsi le operazioni di spostamento non eseguire la migliore:

//bitwise 
if ((x & 1) == 0) 
    //even number 
else 
    //odd number 


System.Math.DivRem((long)x, (long)2, out outvalue); 
if (outvalue == 0) 
    //even number 
else 
    //odd number 


if (((x/2) * 2) == x) 
    //even number 
else 
    //odd number 


//bit shifting 
if (((x >> 1) << 1) == x) 
    //even number 
else 
    //odd number 


index = NumberOfNumbers; 
while (index > 1) 
    index -= 2; 
if (index == 0) 
    //even number 
else 
    //odd number 


tempstr = x.ToString(); 
index = tempstr.Length - 1; 
//this assumes base 10 
if (tempstr[index] == '0' || tempstr[index] == '2' || tempstr[index] == '4' || tempstr[index] == '6' || tempstr[index] == '8') 
    //even number 
else 
    //odd number