Remplacement de “==” par des opérateurs au niveau des bits

En utilisant uniquement les opérateurs au niveau des bits (|, &, ~, ^, >>, <<) et d’autres opérateurs de base tels que +, – et!, Est-il possible de remplacer le "==" ci-dessous?

int equal(int x, int y) { return x == y; } 

    Deux nombres sont égaux s’il n’y a pas de différence entre eux:

     int equal(int x, int y){ return !(xy); } 

    N’oubliez pas qu’un XOR est exactement le même que NOT EQUALS et XNOR est exactement le même que EQUALS . Donc, ce qui suit vous donnera exactement ce que vous voulez:

     return !(x ^ y); 

    Le C ! l’opérateur est vraiment juste un raccourci pour != 0 , donc l’utiliser semble très proche de la sortingcherie 🙂

    Voici ma prise juste en utilisant des opérations au niveau des bits, en supposant qu’une machine de complément à deux bits 32 bits avec des décalages de droite arithmétiques (techniquement, en C arithmétique, les décalages de droite ne sont pas définis, mais chaque compilateur C que j’ai vu sur une machine à complément à deux le supporte correctement):

     int t = (x - y) | (y - x); // <0 iff x != y, 0 otherwise t >>= 31; // -1 iff x != y, 0 otherwise return 1 + t; // 0 iff x != y, 1 otherwise 

    Cela dit, les compilateurs actuels n’ont pas ce problème. Le matériel réel prend en charge directement les comparaisons. Les détails dépendent de l’architecture, mais il existe deux modèles de base:

    1. Les codes de condition renvoyés pour les opérations arithmétiques (par exemple, x86 et ARM le font). Dans ce cas, il existe généralement une instruction “compare” qui soustrait deux valeurs, ne réécrit pas dans un registre entier, mais définit le code de condition / les indicateurs en fonction du résultat.
    2. De plus en plus de plates-formes de type RISC ont généralement des opérandes “twig si égal” et “twig si moins que” qui effectuent une comparaison et une twig en fonction du résultat. C’est fondamentalement équivalent au code C

       if (a == b) goto label; 

      ou

       if (a < b) goto label; 

      tout en une instruction de la machine.

    Cet exemple est identique à la soustraction, mais il est plus explicite sur la manière dont certaines architectures enregistrent la comparaison (comme l’ARM, je crois).

     return !(1 + ~x + y); 

    Le 1 signifie l’entrée du bit de retenue dans l’ALU. Un nombre x est complété au niveau du bit. Prendre le complément et append 1 produit le complément à deux du nombre ( x devient -x ), puis il est ajouté à l’autre nombre pour obtenir la différence et déterminer l’égalité.

    Donc, si les deux nombres sont égaux, vous obtenez -x + x => 0 .

    (Au niveau du registre, l’opérateur ! N’est pas terminé et vous testez simplement le “bit zéro” du registre de codes de condition ou de drapeaux, qui est défini si l’opération du registre produit un résultat égal à zéro et est effacée dans le cas contraire.)

    Comme XOR est identique à (! =), Par conséquent (x ^ y) ne retournera 0 que pour des valeurs égales. Ma prise est la suivante, car elle est judicieuse, utilise un opérateur bit par bit et fonctionne.

     int notEqual(int x, int y){ return (x ^ y); } 

    Ma prise sur ce

     int equal(int x, int y){ if((x & ~y) == 0) return 1; else return 0; } 

    Explication: Si x == y , alors x & ~y égaux à 0 retournent 1, sinon la valeur renvoyée est 0, car x!=y

     Edit1: The above is equivalent to int equal(int x, int y){ return !(x & ~y) ; // returns 1 if equal , 0 otherwise. } 

    Le code ci-dessus échoue dans certains cas où le bit le plus significatif devient 1. La solution consiste à append un 1. c’est-à-dire que la réponse correcte est

     return !(x & (~y +1) );