Comprobar si un número es impar, ¿Cual es la manera mas rápida?

Mi lectura de turno es el aunque medio añejo, muy recomendable libro Java Puzzlers . En este, los autores, que en su mayoría han estado ligados al desarrollo del lenguaje Java en alguna de sus fases nos plantean ejercicios que siempre parece que terminan de una forma y lo hacen de otra, sorprendiéndonos gratamente, desvelándonos alguna de las interioridades del lenguaje y haciéndonos conocerlos un poco mejor.

Uno de los ejercicios gira en torno a conocer en Java si un número es impar. La manera usual de obtener esto es mediante el operador % usando la expresión siguiente:

numero%2!=0

Este operador, en realidad calcula el resto de la división de numero entre 2 y por consiguiente de acuerdo a la especificación del lenguaje seria parte de la siguiente igualdad

numero/2+resto=división

a partir de la cual es calculado.

En Java Puzzlers se nos plantea la alternativa de saber si un número es impar si al aplicarle una operación Bitwise And con 1 como segundo operando devuelve algo distinto de 0

numero & 1!=0

El fundamento de esto es que el operador And Bitwise realiza un And entre las representaciones binarias de ambos operandos. El 1 al representarse en binario solo podrá dar como resultado un numero distinto de 0 al aplicarle un & Bitwise al ser comparado con un numero que también tenga un uno en la ultima posición en binario y estos numero tienen la forma 2n+1 o sea son impares.

000000001
&
________1
=
000000001

Para comprobar la veracidad del planteamiento se ha elaborado un mini programa que dado una entrada de 1 000 000 de números pone en practica ambos métodos para comprobar si son impares y el resultado como podrá verse comprueba lo planteado por los autores.

Ejecutando comprobacion con el mismo valor, 1000000 times
Via usual
Tardo 6 milisegundos
Via Bitwise
Tardo 0 milisegundos
Ejecutando comprobacion con 1000000 valores diferentes
Via usual
Tardo 5 milisegundos
Via Bitwise
Tardo 1 milisegundos




La ligera diferencia que existe entre el caso en el que los números son todos distintos y cuando son iguales no parece repetirse en sucesivos ejecuciones del programa por lo que no debería ser significativa. De esto puede extraerse que aunque usar el bitwise and pueda significar confuso a primera vista para posibles terceros que lean nuestro código, en ocasiones puede significar una mejora importante en el rendimiento de nuestras aplicaciones y es sin duda una cuestión que merece ser conocida por todos los amantes de un código eficiente y optimo.

Solución del problema de los Lucky Tickets

Entre muchas aficiones que tengo, una de ellas es resolver problemas de algoritmia. Soy usuario activo de jurados en línea que no son mas que sitios con bancos de problemas en los cuales el usuario puede registrarse y enviar sus soluciones para que un evaluador automático las califique y de esa forma poder competir con programadores de todo el mundo.

A pesar de haber resuelto mucho ejercicios de este tipo, a menudo me encuentro con que a pesar de haber pasado mucho tiempo pensando en una solución y finalmente de haberla encontrado, al poco tiempo no la recuerdo. Es por esto que me he propuesto la meta de publicar aquí cada solución que envié con una breve explicación de manera que el algoritmo quede descrito para el futuro.

En esta ocasión he resuelto el problema de los Lucky Tickets en lenguaje C#.

using System;
using System.Collections;

class Program
    {
        static void Main(string[] args)
        {
            int x = int.Parse(Console.ReadLine());
            Ticket(x);
         }
        public static void Ticket(int cifras)
        {
            int mitad = cifras / 2;
            int result = 0;
         
            for (int i = 0; i <= 9 * mitad; i++)
            {
                int sum=SumanK(i,mitad);
                result += sum * sum;
            }
            Console.WriteLine(result);
        }

        private static int SumanK(int k, int cifras)
        {
            if (cifras == 1 && k<10)
            {
                return 1;
            }
            int min = Math.Min(k, 9);
            int max = Math.Max(0, k - 9 * (cifras - 1));
            int count = 0;

            for (int i = max; i <= min; i++)
            {
                count=count+SumanK(k - i, cifras - 1);  
            }
            return count;
        }     
    }
Solución:
La solución puede dividirse en 2 partes muy simples. La primera es detectar cuantas distintas sumas existen donde los sumandos sean los dígitos de números de n/2 cifras. De esta forma para por ejemplo n=6, n/2=3--> 9*9*9=27. Las posibles sumas de los dígitos de números de 3 dígitos vas desde 0 hasta 27.

Dicho, esto solo tendríamos que encontrar para cada uno de estos valores de posible suma, que combinaciones de digitos hacen que se pueda obtener la misma. Para esto se usa el algoritmo recursivo implementado mediante la función SumanK, que funciona de esta forma:

Dadas la cantidad de cifras c y el numero a obtener como suma k:

• Si c=1 y k<10 se devuelve 1
• Si c>1 
• El mínimo dígito posible para la ultima posición sería el Máximo entre 0 y k-9*Todos los dígitos restantes
• El máximo dígito posible sería el mínimo entre k y 9
• Iterando desde mínimo hasta máximo (valor i) y se calcula recursivamente cuantos números suman k-i y tienen una cifra menos.