Comment savoir si un nombre est un multiple de quatre en utilisant uniquement l'opérateur logique ET?

Question

Je suis en train de jouer avec la programmation en langage assembleur et je suis curieux de savoir si je pourrais dire si un nombre est un multiple de 4 en utilisant l'opérateur logique ET?

Je sais comment le faire en utilisant les instructions "div" ou "reste", mais j'essaye de le faire avec la manipulation de bits de nombre/mot.

Quelqu'un peut-il me diriger dans la bonne direction? J'utilise des MIP mais une réponse agnostique de Language est correcte.

Answer 1

Eh bien, pour détecter si un nombre est un multiple d'un autre, il suffit de faire x MOD y. Si le résultat est 0, alors il s'agit d'un multiple pair.

Il est vrai aussi que pour chaque y qui est une puissance de 2, (x MOD y) équivaut à (x AND (y - 1)).

Par conséquent:

IF (x AND 3) == 0 THEN 
    /* multiple of 4 */ 

EDIT:

ok, vous voulez savoir pourquoi (x MOD y) == (x AND (y - 1)) quand y est une puissance de 2. Je ferai de mon mieux pour expliquer. Fondamentalement, si un nombre est une puissance de 2, alors il a un seul ensemble de bits (puisque binaire est la base 2). Cela signifie que tous les bits inférieurs sont désactivés. Par exemple: 16 == 10000b, 8 == 1000b, etc.

Si vous soustrayez 1 à l'une de ces valeurs. Vous vous retrouvez avec le bit qui a été mis en place et tous les bits en dessous sont définis. Donc, fondamentalement, il crée un masque qui peut être utilisé pour tester si l'un des bits inférieurs a été défini. J'espère que c'était clair.

EDIT: commentaire de Bastien Léonard couvre bien aussi:

si vous divisez (non signé) 4, vous décaler deux bits vers la droite. Ainsi, le reste est ces deux bits, qui perdent lorsque vous divisez. 4 - 1 = 11b, c'est-à-dire, un masque qui donne les deux bits les plus à droite lorsque vous ET le avec une valeur .

EDIT: voir cette page pour obtenir des explications plus claires possible: http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

Il couvre la détection des puissances de 2 et l'utilisation et comme une opération rapide modulo si elle est une puissance de 2.

Answer 2

(x & 3) == 0

W.r.t. langage d'assemblage, utilisez TST si disponible, sinon ET et vérifiez le drapeau zéro.

Answer 3

Un nombre est un multiple de 4 si ses 2 bits inférieurs sont 0, vous pouvez donc simplement décaler le nombre à droite deux fois et vérifier les bits décalés pour 0.

Answer 4

En assembleur x86:

test eax, 3 
    jnz not_multiple_of_4 

    ; action to be taken if EAX is a multiple of 4 

not_multiple_of_4: 
    ; ...