¿Cómo puedo saber si un número es un múltiplo de cuatro utilizando solo el operador lógico Y?

Question

Estoy jugando con la programación del lenguaje ensamblador y tengo curiosidad por saber si un número es un múltiplo de 4 usando el operador lógico Y?

Sé cómo hacerlo usando las instrucciones "div" o "remainder", pero estoy tratando de hacer esto con la manipulación del número/palabra.

¿Alguien puede indicarme la dirección correcta? Estoy usando MIP pero una respuesta independiente del idioma está bien.

Answer 1

Bueno, para detectar si un número es un múltiplo de otro, simplemente necesita hacer x MOD y. Si el resultado es 0, entonces es un múltiplo par.

También es cierto que por cada y que es una potencia de 2, (x MOD y) es equivalente a (x AND (y - 1)).

Por lo tanto:

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

EDIT:

bien, que quieren saber por qué (x MOD y) == (x AND (y - 1)) cuando y es una potencia de 2. Voy a hacer mi mejor esfuerzo para explicar.

Básicamente, si un número es una potencia de 2, entonces tiene un solo bit establecido (ya que el binario es la base 2). Esto significa que todos los bits inferiores están desarmados. Por ejemplo: 16 == 10000b, 8 == 1000b, etc.

Si resta 1 de estos valores. Terminas con el bit que se configuró como desarmado y todos los bits debajo de él se establecen.

15 = 01111b, 7 = 0111b, etc. Así que, básicamente, se crea una máscara que se puede utilizar para probar si cualquiera de los bits inferiores se establecieron. Espero que eso esté claro.

EDIT: comentario de Bastien Léonard lo cubre bien también:

si se divide (sin firmar) por 4, que cambia de puesto dos bits a la derecha. Por lo tanto, el resto son esos dos bits, que obtienen perdido al dividir. 4 - 1 = 11b, es decir, una máscara que produce los dos bits más a la derecha cuando ANDA con un valor de .

EDIT: ver esta página explicaciones posiblemente más claras: http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

Cubre la detección de potencias de 2 y el uso de Y como una operación de módulo rápido si es una potencia de 2.

Answer 2

(x & 3) == 0

w.r.t. lenguaje ensamblador, use TST si está disponible, de lo contrario Y, y verifique el indicador de cero.

Answer 3

Un número es un múltiplo de 4 si sus 2 bits más bajos son 0, por lo que puede simplemente cambiar el número dos veces a la derecha y comprobar los bits desplazados para 0.

Answer 4

En ensamblador x86:

test eax, 3 
    jnz not_multiple_of_4 

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

not_multiple_of_4: 
    ; ...