Encuentra si un número dado, num es la potencia de 2 o no. Más específicamente, encuentre si el número dado se puede expresar como 2^k donde k >= 1. Devuelva 1 si el número es una potencia de 2, de lo contrario devuelva 0
NOTA:
- Una cantidad de dígitos del número dado, es decir, (num) puede ser mayor que 100.
- No hay ceros a la izquierda antes de un número distinto de cero. Por ejemplo, 0000128 no está en la entrada./li>
Ejemplos:
Entrada: 3
Salida: 0
Explicación: 2^ 0 = 1 donde k >= 1Entrada: 128
Salida: 1
Método 1: usar strings
La idea es dividir repetidamente el número grande (representado como una string) entre 2. Para realizar la división, recorremos los dígitos de derecha a izquierda. Si el último dígito en sí no es divisible por 2, devolvemos 0. De lo contrario, seguimos el método de división de la escuela.
C
/* C program to find whether a number is power of
2 or not */
#include <stdio.h>
#include <string.h>
// Returns 1 when str is power of 2
// Return 0 when str is not a power of 2
int isPowerOf2(char* str)
{
int len_str = strlen(str);
// Sum stores the intermediate dividend while
// dividing.
int num = 0;
// If the input is "1" then return 0
// because 2^k = 1 where k >= 1 and here k = 0
if (len_str == 1 && str[len_str - 1] == '1')
return 0;
// Divide the number until it gets reduced to 1
// If we are successfully able to reduce the number
// to 1 it means input string is power of two if in
// between an odd number appears at the end it means
// string is not divisible by two hence not a power
// of 2.
while (len_str != 1 || str[len_str - 1] != '1') {
// If the last digit is odd then string is not
// divisible by 2 hence not a power of two
// return 0.
if ((str[len_str - 1] - '0') % 2 == 1)
return 0;
int j = 0;
// Divide the whole string by 2. i is used to
// track index in current number. j is used to
// track index for next iteration.
for (int i = 0; i < len_str; i++) {
num = num * 10 + str[i] - '0';
// If num < 2 then we have to take another digit
// to the right of A[i] to make it bigger than
// A[i]. E. g. 214 / 2 --> 107
if (num < 2) {
// If it's not the first index. E.g 214
// then we have to include 0.
if (i != 0)
str[j++] = '0';
// for eg. "124" we will not write 064
// so if it is the first index just ignore
continue;
}
str[j++] = (int)(num / 2) + '0';
num = (num) - (num / 2) * 2;
}
str[j] = '\0';
// After every division by 2 the
// length of string is changed.
len_str = j;
}
// If the string reaches to 1 then the str is
// a power of 2.
return 1;
}
// Driver code.
int main()
{
char str1[] = "12468462246684202468024"
"6842024662202000002";
char str2[] = "1";
char str3[] = "128";
printf("%d\n%d\n%d", isPowerOf2(str1),
isPowerOf2(str2), isPowerOf2(str3));
return 0;
}
C++
// C++ program to find whether a number is power of 2 or
// not
#include <bits/stdc++.h>
using namespace std;
// Returns 1 when str is power of 2
// Return 0 when str is not a power of 2
int isPowerOf2(string str)
{
int len_str = str.size();
// Sum stores the intermediate dividend while
// dividing.
int num = 0;
// If the input is "1" then return 0
// because 2^k = 1 where k >= 1 and here k = 0
if (len_str == 1 && str[len_str - 1] == '1')
return 0;
// Divide the number until it gets reduced to 1
// If we are successfully able to reduce the number
// to 1 it means input string is power of two if in
// between an odd number appears at the end it means
// string is not divisible by two hence not a power
// of 2.
while (len_str != 1 || str[len_str - 1] != '1') {
// If the last digit is odd then string is not
// divisible by 2 hence not a power of two
// return 0.
if ((str[len_str - 1] - '0') % 2 == 1)
return 0;
int j = 0;
// Divide the whole string by 2. i is used to
// track index in current number. j is used to
// track index for next iteration.
for (int i = 0; i < len_str; i++) {
num = num * 10 + str[i] - '0';
// If num < 2 then we have to take another digit
// to the right of A[i] to make it bigger than
// A[i]. E. g. 214 / 2 --> 107
if (num < 2) {
// If it's not the first index. E.g 214
// then we have to include 0.
if (i != 0)
str[j++] = '0';
// for eg. "124" we will not write 064
// so if it is the first index just ignore
continue;
}
str[j++] = (int)(num / 2) + '0';
num = (num) - (num / 2) * 2;
}
// After every division by 2 the
// length of string is changed.
len_str = j;
}
// If the string reaches to 1 then the str is
// a power of 2.
return 1;
}
// Driver code.
int main()
{
string str1 = "12468462246684202468024"
"6842024662202000002";
string str2 = "1";
string str3 = "128";
cout << isPowerOf2(str1) << endl
<< isPowerOf2(str2) << endl
<< isPowerOf2(str3);
return 0;
}
// This code is contributed by Samim Hossain Mondal.
Java
/* Java program to find whether a number
is power of 2 or not */
import java.util.*;
class GFG
{
// returns 1 when str is power of 2
// return 0 when str is not a power of 2
static int isPowerOf2(String s)
{
char []str = s.toCharArray();
int len_str = s.length();
// sum stores the intermediate dividend while
// dividing.
int num = 0;
// if the input is "1" then return 0
// because 2^k = 1 where k >= 1 and here k = 0
if (len_str == 1 && str[len_str - 1] == '1')
return 0;
// Divide the number until it gets reduced to 1
// if we are successfully able to reduce the number
// to 1 it means input string is power of two if in
// between an odd number appears at the end it means
// string is not divisible by two hence not a power
// of 2.
while (len_str != 1 || str[len_str - 1] != '1')
{
// if the last digit is odd then string is not
// divisible by 2 hence not a power of two
// return 0.
if ((str[len_str - 1] - '0') % 2 == 1)
return 0;
// divide the whole string by 2. i is used to
// track index in current number. j is used to
// track index for next iteration.
int j = 0;
for (int i = 0; i < len_str; i++)
{
num = num * 10 + (int)str[i] - (int)'0';
// if num < 2 then we have to take another digit
// to the right of A[i] to make it bigger than
// A[i]. E. g. 214 / 2 --> 107
if (num < 2)
{
// if it's not the first index. E.g 214
// then we have to include 0.
if (i != 0)
str[j++] = '0';
// for eg. "124" we will not write 064
// so if it is the first index just ignore
continue;
}
str[j++] = (char)((int)(num / 2) + (int)'0');
num = (num) - (num / 2) * 2;
}
str[j] = '\0';
// After every division by 2 the
// length of string is changed.
len_str = j;
}
// if the string reaches to 1 then the str is
// a power of 2.
return 1;
}
// Driver code.
public static void main (String[] args)
{
String str1 = "124684622466842024680246842024662202000002";
String str2 = "1";
String str3 = "128";
System.out.println(isPowerOf2(str1) +
"\n"+isPowerOf2(str2) +
"\n"+isPowerOf2(str3));
}
}
// This code is contributed by mits
Python3
# Python3 program to find whether a number
# is power of 2 or not
# returns 1 when str is power of 2
# return 0 when str is not a power of 2
def isPowerOf2(sttr):
len_str = len(sttr);
sttr=list(sttr);
# sum stores the intermediate dividend
# while dividing.
num = 0;
# if the input is "1" then return 0
# because 2^k = 1 where k >= 1 and here k = 0
if (len_str == 1 and sttr[len_str - 1] == '1'):
return 0;
# Divide the number until it gets reduced to 1
# if we are successfully able to reduce the number
# to 1 it means input string is power of two if in
# between an odd number appears at the end it means
# string is not divisible by two hence not a power
# of 2.
while (len_str != 1 or sttr[len_str - 1] != '1'):
# if the last digit is odd then string is not
# divisible by 2 hence not a power of two
# return 0.
if ((ord(sttr[len_str - 1]) - ord('0')) % 2 == 1):
return 0;
# divide the whole string by 2. i is used to
# track index in current number. j is used to
# track index for next iteration.
j = 0;
for i in range(len_str):
num = num * 10 + (ord(sttr[i]) - ord('0'));
# if num < 2 then we have to take another digit
# to the right of A[i] to make it bigger than
# A[i]. E. g. 214 / 2 --> 107
if (num < 2):
# if it's not the first index. E.g 214
# then we have to include 0.
if (i != 0):
sttr[j] = '0';
j += 1;
# for eg. "124" we will not write 064
# so if it is the first index just ignore
continue;
sttr[j] = chr((num // 2) + ord('0'));
j += 1;
num = (num) - (num // 2) * 2;
# After every division by 2 the
# length of string is changed.
len_str = j;
# if the string reaches to 1 then the
# str is a power of 2.
return 1;
# Driver code.
str1 = "124684622466842024680246842024662202000002";
str2 = "1";
str3 = "128";
print("", isPowerOf2(str1), "\n",
isPowerOf2(str2), "\n",
isPowerOf2(str3));
# This code is contributed by mits
C#
/* C# program to find whether a number is power of
2 or not */
using System;
class GFG
{
// returns 1 when str is power of 2
// return 0 when str is not a power of 2
static int isPowerOf2(string s)
{
char []str = s.ToCharArray();
int len_str = str.Length;
// sum stores the intermediate dividend while
// dividing.
int num = 0;
// if the input is "1" then return 0
// because 2^k = 1 where k >= 1 and here k = 0
if (len_str == 1 && str[len_str - 1] == '1')
return 0;
// Divide the number until it gets reduced to 1
// if we are successfully able to reduce the number
// to 1 it means input string is power of two if in
// between an odd number appears at the end it means
// string is not divisible by two hence not a power
// of 2.
while (len_str != 1 || str[len_str - 1] != '1')
{
// if the last digit is odd then string is not
// divisible by 2 hence not a power of two
// return 0.
if ((str[len_str - 1] - '0') % 2 == 1)
return 0;
// divide the whole string by 2. i is used to
// track index in current number. j is used to
// track index for next iteration.
int j = 0;
for (int i = 0; i < len_str; i++)
{
num = num * 10 + (int)str[i] - (int)'0';
// if num < 2 then we have to take another digit
// to the right of A[i] to make it bigger than
// A[i]. E. g. 214 / 2 --> 107
if (num < 2)
{
// if it's not the first index. E.g 214
// then we have to include 0.
if (i != 0)
str[j++] = '0';
// for eg. "124" we will not write 064
// so if it is the first index just ignore
continue;
}
str[j++] = (char)((int)(num / 2) + (int)'0');
num = (num) - (num / 2) * 2;
}
str[j] = '\0';
// After every division by 2 the
// length of string is changed.
len_str = j;
}
// if the string reaches to 1 then the str is
// a power of 2.
return 1;
}
// Driver code.
static void Main()
{
string str1 = "124684622466842024680246842024662202000002";
string str2 = "1";
string str3 = "128";
Console.Write(isPowerOf2(str1) +
"\n"+isPowerOf2(str2) +
"\n"+isPowerOf2(str3));
}
}
// This code is contributed by mits
PHP
<?php
/* PHP program to find whether a number is power of
2 or not */
// returns 1 when str is power of 2
// return 0 when str is not a power of 2
function isPowerOf2($str)
{
$len_str = strlen($str);
// sum stores the intermediate dividend while
// dividing.
$num = 0;
// if the input is "1" then return 0
// because 2^k = 1 where k >= 1 and here k = 0
if ($len_str == 1 && $str[$len_str - 1] == '1')
return 0;
// Divide the number until it gets reduced to 1
// if we are successfully able to reduce the number
// to 1 it means input string is power of two if in
// between an odd number appears at the end it means
// string is not divisible by two hence not a power
// of 2.
while ($len_str != 1 || $str[$len_str - 1] != '1')
{
// if the last digit is odd then string is not
// divisible by 2 hence not a power of two
// return 0.
if (ord($str[$len_str - 1] - '0') % 2 == 1)
return 0;
// divide the whole string by 2. i is used to
// track index in current number. j is used to
// track index for next iteration.
$j=0;
for ($i = 0; $i < $len_str; $i++)
{
$num = $num * 10 + (ord($str[$i]) - ord('0'));
// if num < 2 then we have to take another digit
// to the right of A[i] to make it bigger than
// A[i]. E. g. 214 / 2 --> 107
if ($num < 2)
{
// if it's not the first index. E.g 214
// then we have to include 0.
if ($i != 0)
$str[$j++] = '0';
// for eg. "124" we will not write 064
// so if it is the first index just ignore
continue;
}
$str[$j++] = chr((int)($num / 2) + ord('0'));
$num = ($num) - (int)($num / 2) * 2;
}
// After every division by 2 the
// length of string is changed.
$len_str = $j;
}
// if the string reaches to 1 then the str is
// a power of 2.
return 1;
}
// Driver code.
$str1 = "124684622466842024680246842024662202000002";
$str2 = "1";
$str3 = "128";
print(isPowerOf2($str1)."\n".isPowerOf2($str2)."\n".isPowerOf2($str3));
// This code is contributed by mits
?>
?>
Producción
0 0 1
Complejidad de tiempo: O(N^2) donde N es un número de dígitos en el número dado.
Método 2: uso de la biblioteca
Boost Las bibliotecas Boost están diseñadas para ser muy útiles y utilizables en un amplio espectro de aplicaciones. Por ejemplo, son útiles para manejar números grandes que tienen un rango más allá del tipo de datos long long, long double (264) en C++.
- Tome la entrada como un impulso entero.
- Usando la manipulación de bits, verifique si es el poder de 2 o no.
C++
// C++ program to find whether a number
// is power of 2 or not
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;
// Function to check whether a
// number is power of 2 or not
bool ispowerof2 ( cpp_int num )
{
if ( ( num & ( num - 1 ) ) == 0 )
return 1;
return 0;
}
// Driver function
int main()
{
cpp_int num = 549755813888;
cout << ispowerof2 ( num ) << endl;
return 0;
}
// This code is contributed by Aditya Gupta 4
Java
// Java program to find
// whether a number
// is power of 2 or not
class GfG
{
// Function to check whether a
// number is power of 2 or not
static long ispowerof2 ( long num )
{
if ((num & (num - 1)) == 0)
return 1;
return 0;
}
// Driver code
public static void main(String[] args)
{
long num = 549755813888L;
System.out.println(ispowerof2(num));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to find whether a number # is power of 2 or not # Function to check whether a # number is power of 2 or not def ispowerof2(num): if((num & (num - 1)) == 0): return 1 return 0 # Driver function if __name__=='__main__': num = 549755813888 print(ispowerof2(num)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to find
// whether a number
// is power of 2 or not
class GFG{
// Function to check whether a
// number is power of 2 or not
static long ispowerof2 ( long num )
{
if ((num&(num-1)) == 0)
return 1;
return 0;
}
// Driver Code
public static void Main()
{
long num = 549755813888;
System.Console.WriteLine(ispowerof2(num));
}
}
// This code is contributed
// by mits
PHP
<?php
// PHP program to find
// whether a number
// is power of 2 or not
// Function to check whether a
// number is power of 2 or not
function ispowerof2 ( $num )
{
if (($num & ($num - 1 )) == 0)
return 1;
return 0;
}
// Driver Code
$num = 549755813888;
echo ispowerof2($num);
// This code is contributed
// by mits
?>
Javascript
<script>
// Javascript program to find
// whether a number
// is power of 2 or not
// Function to check whether a
// number is power of 2 or not
function ispowerof2(num)
{
if ((num & (num - 1)) == 0)
return 1;
return 0;
}
// Driver code
var num = 549755813888;
document.write(ispowerof2(num));
// This code is contributed by Princi Singh
</script>
Producción
1
Método: uso de operadores lógicos y bit a bit
C++
// C++ code to check if HUGE number
// is a power of two or not.
#include <iostream>
using namespace std;
int main()
{
long int x = 128;
// condition to check if given
// number is power of 2 or not
if (x and (not(x & (x - 1)))){
cout<<"Yes";
}
else
{
cout<<"No";
}
return 0;
}
Python3
#python code to check if HUGE number
# is a power of two or not.
x=128
# condition to check if given
# number is power of 2 or not
if (x and (not(x & (x - 1)))):
print("yes")
else:
print("no")
Javascript
<script>
var x = 128;
// condition to check if given
// number is power of 2 or not
if (x and (not(x & (x - 1))))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by ksrikanth0498
</script>
Producción
yes
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Referencia: https://www.boost.org/doc/libs/1_61_0/libs/multiprecision/doc/html/index.html
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente. .
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA