programa en C ++ para comprobar si el número es potencia de 2 utilizando operador Bitwise

En este artículo, vamos a aprender a comprobar si un número dado es la potencia de 2 o no el uso de operador de bits ?

Dado un número y tenemos que comprobar si es potencia de 2 o no.

Un enfoque obvio es dividir el número por 2 hasta que el número no conseguirá 0 o 1. Sin embargo, este algoritmo tiene el problema de la Complejidad de tiempo. Este algoritmo toma la O (log (n)) complejidad de resolver un problema tan simple.

Así cómo podemos mejorar esto? , Puede esto ser resuelto con el fin de O (1) la complejidad?

La respuesta a esto es “sí”, con la ayuda del operador de bits .

embargo, antes de esto, tenemos que saber acerca de una propiedad simple del número binario que es “el poder de 2, que tiene un solo bit activado en su representación binaria” .

class ejemplo,

     2 =    0001
4 = 0100
8 = 1000
16 = 10000
32 = 100000
64 = 1000000
so on..

Ahora, vamos a ser más precisos acerca de esto,

Si restamos 1 de la potencia de 2 lo que obtenemos es 1s en todos los lugares de la final del número binario hasta que no obtendrá 1 bit activado. Y, si aplicamos el operador AND bit a bit sólo deberíamos obtener ceros.

Esto conseguirá más claro con este ejemplo:

    Let the no n =16
Binary representation of 16 is
16 = 0 0 0 1 0 0 0 0
16-1= 0 0 0 0 1 1 1 1
----------------------------
Now 16 AND 15= 0 0 0 0 0 0 0 0
Hence , 16 is the power of 2
But what in case if it is not:
Let the no n=15
15 = 0 0 0 0 1 1 1 1
14 = 0 0 0 0 1 1 1 0
----------------------------
15 AND 14= 0 0 0 0 1 1 1 1
So 15 is not the power of 2.

Ahora bien, esto puede ser implementado con orden de complejidad 1

    if (n & (n-1) == 0) return true;

Ejemplo:

    INPUT:
n = 4
n-1 = 3
n & n-1 = 0
(AND of 100 with 011)
Output= TRUE
INPUT:
n = 9
n-1 = 8
n & n-1 = 9
(AND of 1001 with 1000)
Output= FALSE
INPUT:
n = 15
n-1 = 14
n & n-1 = 14
(AND of 01111 with 01110)
Output=FALSE
INPUT:
n = 16
n-1 = 15
n & n-1 = 0
(AND of 10000 with 01111)
Output= TRUE

C ++ aplicación

// program to find that the number is power of 2
#include<iostream>
using namespace std;
int main()
{
// declaring the array n
int n[]={4,9,15,16,20,22,25,32,45,64,72,80,100,128,256};
int i;
for(i=0;i<15;i++)
{
cout<< n[i] << " is power of 2 : ";
// use of bitwise AND (&) operator
if((n[i]& (n[i]-1))==0)
cout<<"True"<<endl;
else
cout<<"False"<<endl;
}
return 0;
}

salida

4 is power of 2 : True 
9 is power of 2 : False
15 is power of 2 : False
16 is power of 2 : True
20 is power of 2 : False
22 is power of 2 : False
25 is power of 2 : False
32 is power of 2 : True
45 is power of 2 : False
64 is power of 2 : True
72 is power of 2 : False
80 is power of 2 : False
100 is power of 2 : False
128 is power of 2 : True
256 is power of 2 : True


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *