Pregunta C# (7 de 20): ¿Cómo Comprobar si un Número es Potencia de 2?

Índice

0. Introducción
1. Contexto
1.1 ¿Qué significa obtener la potencia de un número?
2. Determinar si un Número es Potencia de 2
2.1 Proceso manual
2.2 Comprobación en C#
3. Recursos
4. Conclusiones
5. Glosario
6. Literatura & Enlaces

0. Introducción

Pasemos a la séptima pregunta para conocer uno de los medios de validación o comprobación de si un número dado es potencia de 2. Para llevar a cabo esta comprobación utilizaremos especialmente la operación lógica AND. Para esto tendremos que hacer algunas manipulaciones matemáticas básicas, como convertir la representación decimal (base 10) a representación binario (base 2), y luego aplicar la operación lógica mencionada y por último comprobar que el resultado (en decimal) es distinto de cero. Este mismo proceso lo implementaremos usando el lenguaje de programación C#. ¡Empecemos!

1. Contexto

1.1 ¿Qué significa obtener la potencia de un número?

Obtener la potencia de un número consiste en una operación aritmética fundamental que simplifica la operación de producto. Es decir, en lugar de escribir:

podemos hacerlo a través de esta representación simplificada: 

Esta última representación se puede leer de la siguiente manera: 2 a la n, consiste en usar n veces 2 en multiplicaciones sucesivas por sí mismo.

Un ejemplo particular sería:

Que se podría leer de la siguiente: multiplíquese 2 por sí mismo 3 veces:

En general, la representación de la potencia queda de la siguiente manera:

Figura 1. Representación general potencia.

2. Determinar si un número es potencia de 2

2.1 Proceso manual

Este es el conjunto de pasos a seguir para comprobar si un número es potencia de 2:

Paso 1: Comprobar que el número sea diferente de 0.

Pase 2: Convertir el número a representación binaria.

Paso 3: Al número original restarle 1.

Paso 4: Convertir a binario el valor obtenido de la diferencia (Paso 3).

Paso 5: Realizar la operación lógica AND entre las dos representaciones binarias obtenidas (Paso 2, y Paso 4).

Paso 6: El número es potencia de 2 si el resultado del operación lógica AND es 0, de lo contrario el número dado no es potencia de 2.

Comprobaremos que el número 8 es potencia de 2. En la Figura 2 se describe el proceso realizado a mano:

Figura 2. Comprobación 8 como potencia de 2.

Ahora sigamos los mismos pasos comprobar si 11 es potencia de 2:

Figura 3. Comprobación 11 como potencia de 2.

2.2 Comprobación en C#

¿Cómo llevamos a cabo esta operación en C#? Este lenguaje de programación cuenta con operadores a nivel de bits: bitwise (o bit-a-bit). (En el artículo Operadores Bitwise podrán encontrar una explicación con más detalles sobre estos operadores).

El operador & (AND) de forma implícita convierte los operandos enteros a su representación binaria de una expresión y luego opera a nivel de bits. Creemos un programa de demostración en C# para conocer este proceso:

Archivo C# ComprobacionPotenciaDe2.cs [enlace alternativo]:

En las líneas 31-40 se declara el método EsPotenciaDe2 con el que implementamos la lógica de comprobación de si un número es potencia de 2:

• Primero validamos que el número pasado como argumento al método EsPotenciaDe2 sea distinto de 0: numero != 0
• Enseguida, substraemos una unidad del valor del argumento: numero - 1
• Realizamos la operación bitwise AND entre el valor original del argumento y el valor obtenido por la diferencia anterior: numero & (numero - 1)
• Pasamos a comprobar si el valor decimal resultante de la operación bitwise AND previa es igual 0. De ser así el número es potencia de 2, en caso contrario, no lo es.

Vale resaltar el que tipo del argumento en este caso es un ulong debido a que en esta operación nivel de bits sólo nos interesa los números enteros positivos en su representación binaria.

Compilación:

1. csc /target:exe ComprobacionPotenciaDe2.cs

Ejecución assembly:

1. .\ComprobacionPotenciaDe2.exe

> Prueba de ejecución (ideone.com).

> Prueba de ejecución (local):

Figura 4. Ejecución assembly ComprobacionPotenciaDe2.exe.

3. Recursos

Este es el vídeo en donde el equipo de expertos (Gerry O'Brein y Paul Pardi) de MVA responden y explican esta pregunta:

4. Conclusiones

A través de esta pregunta en C# pudimos comprobar si un número entero dado es potencia de 2. Importante el contacto y uso de los operadores bitwise de los que dispone C# para llevar cabo este requerimiento. El uso de estos operadores es mucho más eficiente que realizar las operaciones que sólo manipulen la representación entera decimal. En la próxima pregunta resaltaremos las diferencias entre las construcciones break y continue en un ciclo.

5. Glosario

• AND
• Bit-a-bit
• Bitwise
• Ciclo
• Entero
• Operación bitwise
• Operador

6. Literatura & Enlaces

[1]: Twenty C# Questions Explained - http://www.microsoftvirtualacademy.com
[2]: Operadores Bitwise (Bit a Bit) en C# | OrtizOL - Experiencias Construcción Software (xCSw) - http://ortizol.blogspot.com/2013/07/operadores-bitwise-bit-bit-en-c.html

A