Cargando...
 
Imprimir

Algoritmo para saber si un número es par o impar, o de como enrollarse con un tema de lo más tonto

Image
Saber si un número entero dado es par o impar dentro de un programa es algo sencillo.... cuando te lo cuentan :-)

En éste artículo proponemos varias formas de lograrlo, intentando descubrir los pros y los contras de cada uno.

Este es un ejercicio típico de cualquier asignatura o curso de programación en sus primeros días, para intentar despabilar un poco las neuronas. Las posibles formas de solucionarlo son muy variadas. Vamos a ver sólo unas pocas de ellas, empezando con la más sensata para la mayor parte de las situaciones, y también veremos algunas menos sensatas y otras realmente descabelladas.



1) Con aritmética modular, o utilizando el resto de una división entera

Ésta es, en general, la solución más sensata.

La operación denominada "módulo" está instrumentada en prácticamente todos los lenguajes de programación. Hace referencia al resto de la división entera entre dos números.

Es decir, si cogemos dos números enteros, como por ejemplo el 79 y el 14 y dividimos 79 entre 14 utilizando la división entera (sin decimales), el cociente que obtenemos es 5, y el resto (o módulo) es 9.

En muchos lenguajes de programación, se utiliza el operador binario infijo mod para obtener el módulo de una division (Como Pascal, Modula, Delphi...). Otros muchos lenguajes (C, C++, C#, Java, PHP...) utilizan otro operador binario infijo: %. Es posible que otros lenguajes utilicen un método o función o bien otro operador.

El caso es que si nos damos cuenta, cualquier número par tiene una característica: si lo dividimos por dos, el resto de la operación es 0. Análogamente, si un número impar lo dividimos por dos siempre devuelve 1 como resto.

¡¡¡Ya lo tenemos!!! Dado un número n, si el resto de dividir n entre 2 es 0, resulta que n es par, y en caso contrario es impar.

Hala, ya podemos construir un método o función bien sencillo. Como de momento todos los ejemplos de este sitio están en C#, vamos a proponer un método en éste lenguaje llamado "EsPar", al cual le pasemos un entero y nos devuelva un booleano con un valor true si el entero es par y false en caso contrario, basándonos en la operación módulo.

C#
static bool EsPar(int n)
   {
      return ((n % 2) == 0); 
   }


El operador módulo sirve para muchísimas más cosas. De hecho, el matemático Carl Friedrich Gauss(external link) presentó formalmente la aritmética modular, basada en el resto de las divisiones que abrió un apasionante campo dentro de la teoría de números(external link) y por extensión, de la matemática discreta(external link). Por supuesto, todo ello ha tenido aplicación en el campo de la computación, extendiéndose a materias tan diversas como encriptación, compresión, gráficos, algoritmia, etc, mucho más allá de saber si un número es par o impar.

2) Con la operación AND a nivel de bits, o de como hacer suposiciones arriesgadas

Sabemos que los números enteros son, en general, representados por los computadores utilizando numeraciones binarias, bien con la técnica denominada signo y magnitud(external link), o mucho más frecuentemente en complemento a 2(external link).

En ambos casos, la representación binaria de cualquier entero cumple que en su bit menos significativo (LSB - Least significative bit) hay un valor "1" si el número es impar, y un valor "0" si el número es par. Eso se deriva de la propia naturaleza de la numeración binaria.

Si dado un número n, hacemos la operación AND a nivel de bits con la representación del 1 (un 1 en el LSB y ceros en el resto) resulta que el resultado es el número entero "1" en el caso de que el entero "n" tuviera un 1 en su LSB, y el número entero "0" en el caso de que el entero "n" tuviera un 0 en su LSB. Es decir, en el caso de que n fuera impar o par respectivamente.

Veamos un ejemplo en complemento a 2. Tomemos el número 5 con cuatro bits. En complemento a 2 su representación es "0101". Si hacemos la operación AND con el número 1 en complemento a 2, que es "0001", el resultado es "0001".

0101 AND
0001 =
----
0001


Ahora el mismo ejemplo con el -6 en complemento a 2. Su representación es 1010

1010 AND
0001 =
----
0000


Hala... pues ya tenemos la pista para construir un método en C# que nos diga si un número es par o impar. Como C# utiliza el complemento a dos para la representación interna de los enteros, hacemos la operación AND con 1 y si el resultado es 1 es que es impar, y si es 0 es que es par.

C#
static bool EsPar(int n) 
   {  
      return ((n & 1) == 0); 
   }


(Nota: En C# y otros lenguajes similares, la operación AND a nivel de bits se representa con el operador binario infijo "&". No confundir con la operación lógica AND que se representa con el operador "&&".)

Funcionar, funciona, pero esconde un pequeño peligro. Me he basado en una suposición que no tiene por qué ser cierta: he supuesto que la representación interna del entero está en complemento a 2. Esto es cierto en este momento para la mayor parte de los ordenadores y lenguajes que hay ahora mismo en el mundo... pero no tiene por qué ser así para todos los ordenadores y/o lenguajes que hay ahora mismo ni tampoco para los futuros. En principio, un entero es un entero y tiene una serie de propiedades por ser entero, pero por el hecho de tener una representación interna concreta adquiere otras propiedades digamos adicionales. Nos hemos basado en una de ellas suponiendo cuál es la representación interna. Por poner un ejemplo, si un computador utilizase un código de Gray(external link) para representar enteros, este método no valdría.

avisoCuidado
Así pues, esta forma de saber si un número es par o impar es muy poco recomendable.


3) Con la potencia de -1, o de cómo matar moscas a cañonazos

Pues sí. Resulta que si cogemos el número -1, y lo multiplicamos por sí mismo, el resultado es 1 (positivo), pero si lo volvemos a multiplicar por -1, el resultado es -1 de nuevo, y si ese resultado lo volvemos a multiplicar por -1, otra vez obtenemos 1 (positivo).

Podemos decir que en general, si elevamos el número -1 a una potencia n, el resultado es -1 si n es impar, y 1 si n es par. Así pues, para saber si un número dado n es par o impar, podemos aplicar la siguiente expresión:
p(n)=(-1)|n|


Si n es par entonces p(n) es 1. Si n es impar entonces p(n) es -1.

Estupendo. ¿Cuál es el problema entonces? Problema como tal, ninguno, peeeeero aunque los lenguajes de programación suelen incorporar funciones o métodos para calcular las potencias, estos en general y a pesar de que tienen un coste prácticamente constante, suelen ser internamente más complicados que hallar el resto de una división, como se proponía en la primera solución. Normalmente, incluso operan en coma flotante, y no con aritmética entera. Las operaciones con aritmética entera suelen ser menos costosas en su ejecución. Nadie puede decir que esta forma de saber si un número es par no sea correcta o encierre algún peligro -como en el caso 2)-, pero sí que nos pueden decir que existe otra forma más sencilla.

En este ejemplo en C# utilizamos dos métodos de librería, pero el método Pow, para calcular la potencia trabaja con coma flotante. Sin embargo, -1 y n son ambos enteros.

C#
static bool EsPar(int n) 
   {  
      return Math.Pow(-1, Math.Abs(n))>0; 
   }


Si para evitar la operación Pow se nos ocurre utilizar un bucle, nos iríamos a un caso muchísimo peor, porque cambiaríamos una complejidad prácticamente constante por una lineal.

4) Divisiones encubiertas, o de cómo darle vueltas a lo mismo.

Es posible encontar soluciones que son prácticamente equivalentes a las anteriores... es decir, darle vueltas a lo mismo.

Por ejemplo. Si dado un número entero n lo dividimos por 2 despreciando el resto y lo volvemos a multiplicar por 2, en el caso de que n sea par el resultado de la operación será el mismo número n. Si n fuera impar, el resultado de dividir por 2 y volver a multiplicar no da de nuevo el número n.

Tanto si n es par como impar, vamos a despreciar el resto de la división, pero si n es par el resto de la división es 0, con lo cual, al volver a multiplicar por 2 obtenemos de nuevo n.

Podemos utilizar ésto para construir nuestro método para saber si n es par:

C#
static bool EsPar(int n)
   {  
      return (n/2)*2==n; 
   }


Pero realmente, lo que estamos haciendo es intentar averiguar si el resto de la división de n entre 2 es 0 o no. Así que esta solución es muy parecida a la 1)

También podríamos haber utilizado el desplazamiento de bits. Desplazar bits a la derecha en un número binario es realmente, dividirlo por 2.

Por ejemplo, si tomamos el número 76, en binario es 1001100.
Si desplazamos a la derecha ese número binario y rellenamos el hueco que queda a la izquierda con un 0, obtenemos 0100110, que es el 38.
Volvamos a desplazar a la izquierda, rellenando con 0 el lugar que queda por la derecha... obtenemos de nuevo el 1001100.

Ahora vamos a probar con el 77. En binario es 1001101.
Desplazamos a la derecha: 0100110, que es el 38.
Desplazamos a la izquierda: 1001100.... oops... Es el 76.

Si desplazamos un número binario hacia la derecha y luego hacia la izquierda, realmente dividimos por 2 y volvemos a multiplicar por 2.

En esta operación, un número par perderá su 0 en el bit menos significativo (LSB) y luego lo recuperará, pero un número impar perderá su 1 del LSB y luego recuperará un 0.

C#
static bool EsPar(int n) 
   {  
      return ((n>>1) << 1) == n; 
   }


ésto se le pueden poner un par de pegas importantes: esto es, de nuevo, comprobar si el resto de la división por 2 es 0 y además, se basa en suposiciones acerca de la codificación del entero n.

5) Utilizando bucles, o de cómo solucionar un problema sencillo con una solución tonta


En esta escalada de malas soluciones, podríamos llegar al caso de meternos a hacer bucles. Las variedades de bucles que podemos hacer son muchas.

Por ejemplo, podríamos utilizar la potencia de -1 que hemos visto en el punto 3), pero en lugar de utilizar una función de librería para hallarla, meternos con un bucle:

C#
static bool EsPar(int n) 
   {
      //hallar el valor absoluto de n  
      int vabs = n;
      if (vabs < 0)  
      {
         vabs = -vabs; 
      }  
      //contar desde 0 hasta el valor absoluto de n
      int resultado = -1;
      for (int i = 0; i <= vabs; i++)
      {
          resultado *= -1; 
      }
      return resultado>0; 
   }


O utilizar una variable booleana, contar desde 0 hasta el valor absoluto de n, y en la primera iteración del bucle ponerla a true, la siguiente a false, la siguiente a true...

C#
static bool EsPar(int n)  
   {  
      //hallar el valor absoluto de n  
      int vabs = n;
      if (vabs < 0)
         vabs = -vabs; 
      //contar desde 0 hasta el valor absoluto de n
      bool resultado = false;
      for (int i = 0; i <= vabs; i++)
         {
             resultado = !resultado; 
         }  return resultado; 
   }


6) Utilizando recursividad, o de como solucionar un problema sencillo con una solución paranóica


Si la solución anterior con bucles no era buena, lo que resulta realmente descabellado es utilizar recursividad. Además de implicar una complejidad lineal, estaremos propiciando un desbordamiento de pila? (stack overflow).

El tema se puede abordar de muchas formas. Por ejemplo... podemos utilizar como caso base de la recursividad que si n=0, entonces n es par, y como caso general que si n>0, entonces la paridad de n es la contraria que la de n-1. Eso sí, siempre que n sea posivito. Como la paridad es simétrica con respecto al 0 (es decir, n y -n tienen la misma paridad), tomaremos el valor absoluto de n.

C#
static bool EsPar(int n) 
   {
      if (n == 0)  
         {
            //caso base
            return true;
         } 
      else
         {
            //caso general
            //k es el valor absoluto de n
            int k = (n < 0) ? -n : n;
           //la paridad de k es la contraria
           //que la de k-1
           return !EsPar(k-1); 
         }
    }


Conclusión


En fin... a veces hay varias formas de hacer las cosas. Cuando esto ocurre, conviene pararse un poco a meditar cuál es la más conveniente, tanto desde el punto de vista del trabajo que realiza nuestro algoritmo como desde el punto de vista de que funcione en cualquier caso. Explorar las posibles formas de resolver un problema es fantástico para conocerlas, pero en la práctica, es necesario conocer cuál es la mejor opción con un cierto sentido crítico. Esto, realmente, es aplicar la ley del mínimo esfuerzo a nuestros algoritmos y a nuestras vidas ;-) Si nuestros algoritmos realizan su cometido con el menor esfuerzo posible y además los pensamos con un poco de cuidado para que funcionen en cualquier situación, las máquinas que los ejecuten andarán más desahogadas, los dueños de las máquinas serán más felices, y de paso nosotros también, porque nadie nos darán la paliza diciendo que un miserable método para saber si un entero es par está dando problemas.


Ultima edición por vic .
Página última modificacion en Viernes 17 de Agosto, 2012 15:39:23 CEST.



¿Dónde estoy?

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.
Leer más / Términos de uso (ToS)