Come posso sapere se un numero è un multiplo di quattro utilizzando solo l'operatore logico AND?

Question

Sto scherzando con la programmazione del linguaggio assembly e sono curioso di sapere se un numero è un multiplo di 4 utilizzando l'operatore logico AND?

So come farlo utilizzando le istruzioni "div" o "resto" ma sto cercando di farlo con la manipolazione di bit di numero/parola.

Qualcuno può indicarmi la giusta direzione? Sto usando i MIP ma una risposta agnostica della lingua va bene.

Answer 1

Bene, per rilevare se un numero è un multiplo di un altro, è sufficiente eseguire x MOD y. Se il risultato è 0, allora è un multiplo pari.

È anche vero che per ogni che è una potenza di 2, (x MOD y) equivale a (x AND (y - 1)).

Pertanto:

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

EDIT:

ok, volete sapere il motivo per cui (x MOD y) == (x AND (y - 1)) quando y è una potenza di 2. Farò del mio meglio per spiegare.

Fondamentalmente, se un numero è una potenza di 2, quindi ha un singolo bit impostato (poiché binario è base 2). Ciò significa che tutti i bit più bassi sono disattivati. Ad esempio: 16 == 10000b, 8 == 1000b, ecc.

Se si sottrae 1 da uno qualsiasi di questi valori. Si finisce con il bit che è stato impostato non impostato e tutti i bit sotto di esso vengono impostati.

15 = 01111b, 7 = 0111b, ecc. Quindi, in pratica, viene creata una maschera che può essere utilizzata per verificare se è stato impostato uno dei bit inferiori. Spero che sia stato chiaro.

EDIT: commento di Bastien Léonard copre bene anche:

se si divide (non firmato) da 4, si spostare due bit verso destra. Quindi il resto è quei due bit, che ottengono perso quando si divide. 4 - 1 = 11b, ovvero una maschera che produce i due bit più a destra di quando si ERO con un valore .

EDIT: veda questa pagina di spiegazioni possibilmente più chiare: http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

Copre rilevare potenze di 2 e con E come un'operazione di modulo veloce se è una potenza di 2.

Answer 2

(x & 3) == 0

W.r.t. linguaggio assembly, utilizzare TST se disponibile, altrimenti AND, e controllare il flag zero.

Answer 3

Un numero è un multiplo di 4 se i suoi 2 bit inferiori sono 0, quindi è sufficiente spostare il numero a destra due volte e verificare i bit spostati per 0.

Answer 4

In assembly x86:

test eax, 3 
    jnz not_multiple_of_4 

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

not_multiple_of_4: 
    ; ...