Identifier les nombres impairs, pairs - binaires vs mod

Récemment, j'ai eu à déterminer si un nombre est pair ou impair pour un grand nombre d'entiers. J'ai pensé à une idée pour identifier un numéro pair ou impair par ET-ing contre 1 et en comparant le résultat à 1

x & 1 == 1 //even or odd

Je n'ai jamais vu cette mise en œuvre dans la pratique. La façon la plus commune vous voyez toujours est :

x % 2 == 0

J'ai décidé de procéder à une vérification de rendement sur les deux méthodes et la méthode binaire semble légèrement plus rapide sur ma machine.

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();

Quelqu'un a vu la méthode binaire mis en œuvre ? - Il des inconvénients ?

source d'informationauteur Ender

  1. 18

    Bien, oui, c'est une légère optimisation. Cet extrait de code:

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

    génère ce code machine dans la version de publication:

                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

    Noter que le compilateur JIT est assez intelligent pour utiliser le processeur ET l'instruction. Il n'est pas faire une division, comme l'opérateur % feriez habituellement. Bravo.

    Mais votre custom test (test personnalisé génère ce code:

            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

    J'ai dû modifier l'instruction d'assignation, parce que le compilateur JIT eu soudainement intelligent et évalué l'expression au moment de la compilation. Le code est très similaire, mais les ET les instructions ai remplacé par une instruction de TEST. Économie d'une instruction dans le processus. Assez ironique de constater comment cette fois-ci choisi de pas utiliser un ET l' 🙂

    Ces sont les pièges de formuler des hypothèses. L'original de votre instinct avait raison cependant, il devrait permettre d'économiser environ la moitié d'un ordre de la nanoseconde. Très dur de voir que de dos, à moins que ce code de vie dans une très serrée de la boucle. Il devient radicalement différent lorsque vous modifiez la variable de uint int, le compilateur JIT puis génère du code qui essaie d'être intelligent sur le bit de signe. Inutilement.

  2. 4

    Pour de telles opérations, vous devriez préférer la plus lisible approche (à mon avis le modulo) sur celui qui est pensé pour être plus rapide.

    En outre, le modulo ci-dessus peut être optimisé par le compilateur dans le bit-à-bit-et de l'exploitation. Donc, vous avez réellement n'avez pas besoin de soins.

    Note à votre exemple: Pour obtenir plus de précision les résultats envisager de passer le nombre d'éléments à ajouter dans la liste du constructeur. De cette façon, vous éviter les écarts introduits par plusieurs réaffectation de la sauvegarde de la matrice. Pour 60 millions d'éléments entiers (approc. 240 MO de mémoire) pas preallocating la mémoire peut représenter un biais important.

  3. 3

    Cette page web indicateurs de référence au moins une demi-douzaine de façons de déterminer si un nombre est pair ou impair.

    Le plus rapide était (que j'aime pour une meilleure lisibilité):

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

    Ici ont été testé (le code est ici). Je suis d'ailleurs surpris que le bit à bit et bit décalage des opérations n'a pas d'effectuer le meilleur:

    //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
  4. 1

    Au niveau du bit et va battre modulo division tous les jours de la semaine. La Division par un nombre arbitraire prend beaucoup de cycles d'horloge, alors qu'au niveau du bit et est un élément essentiel primitive de l'op qui est presque toujours complète en 1 cycle d'horloge, peu importe votre architecture du PROCESSEUR.

    Ce que vous pouvez voir, cependant, c'est que le compilateur peut être remplacer x mod 2 avec un décalage de bits ou de masque de bits de l'instruction qui aura performance identique à votre propre masque de bits opération.

    Pour confirmer que le compilateur joue des tours avec votre code, de comparer les performances de x mod 2 avec x mod 7 ou tout autre non-base 2 entier. Ou occulter les opérandes de le compilateur de sorte qu'il ne peut pas effectuer l'optimisation:

    var y = 2;
result = x mod y;

    Si vous voyez une différence dramatique dans le temps d'exécution avec ces changements, alors que c'est un assez bon indicateur que le compilateur est le traitement de x mod 2 comme un cas particulier et non pas à partir de la division de trouver le reste.

    Et si vous allez utiliser DateTime pour référence d'instruction unique des opérations, assurez-vous que vous avez une assez longue boucle qui fonctionne le test au moins 5 minutes pour obtenir votre véritable mesure au-dessus du plancher de bruit.

  5. 0

    Ne serait pas la méthode binaire être plus rapide, car le compilateur est capable d'optimiser ce dans un bitshift plutôt que de forcer le cpu pour effectuer la division de calcul?

  6. 0

    Je suis d'accord avec les autres réponses, que vous devez utiliser le modulo vérifier, parce qu'il exprime l'intention.

    Toutefois, pour vos résultats spécifiques; essayez d'utiliser la even variable. Il va faire une grande différence, parce que le compilateur peut réellement optimiser une partie des calculs parce qu'il sait qu'il n'aura pas besoin d'utiliser la valeur.

    À l'aide de votre programme (modifié pour utiliser le Chronomètre), je reçois à 70 ms régulière de la mod et 88 ms pour l'opération binaire. Si j'utilise le even variable, la différence est beaucoup plus petit (327 vs 316 ms), et les modulos est la plus rapide.

  7. 0

    Pour les nombres non signés, de nombreux compilateurs permettra d'optimiser le mod' opérateur 'et' test. Pour les nombres signés, (x % 2) sera 1 si le nombre est impair et positive; -1 si c'est bizarre et négatifs; même si les deux +1 et -1 sont non nuls, il peut ne pas être reconnu comme équivalent.

    BTW, lors de l'utilisation de l'opérateur "et", je test pour !=0 au lieu de ==1. Les compilateurs peuvent reconnaître l'équivalence, mais ils ne peuvent pas.