Escribe una función que, para un no n dado, encuentre un número p que sea mayor o igual que n y sea la potencia más pequeña de 2.
Ejemplos:
Entrada: n = 5
Salida: 8Entrada: n = 17
Salida: 32Entrada: n = 32
Salida: 32
Hay muchas soluciones para esto. Tomemos el ejemplo de 17 para explicar algunos de ellos.
Método 1 (usando el registro del número)
1. Calculate Position of set bit in p(next power of 2): pos = ceil(lgn) (ceiling of log n with base 2) 2. Now calculate p: p = pow(2, pos)
Ejemplo :
Let us try for 17 pos = 5 p = 32
Método 2 (Al obtener la posición de solo el bit establecido en el resultado)
/* If n is a power of 2 then return n */ 1 If (n & !(n&(n-1))) then return n 2 Else keep right shifting n until it becomes zero and count no of shifts a. Initialize: count = 0 b. While n ! = 0 n = n>>1 count = count + 1 /* Now count has the position of set bit in result */ 3 Return (1 << count)
Ejemplo :
Let us try for 17 count = 5 p = 32
C++
// C++ program to find // smallest power of 2 // greater than or equal to n #include <bits/stdc++.h> using namespace std; unsigned int nextPowerOf2(unsigned int n) { unsigned count = 0; // First n in the below condition // is for the case where n is 0 if (n && !(n & (n - 1))) return n; while( n != 0) { n >>= 1; count += 1; } return 1 << count; } // Driver Code int main() { unsigned int n = 0; cout << nextPowerOf2(n); return 0; } // This code is contributed by rathbhupendra
C
#include<stdio.h> unsigned int nextPowerOf2(unsigned int n) { unsigned count = 0; // First n in the below condition // is for the case where n is 0 if (n && !(n & (n - 1))) return n; while( n != 0) { n >>= 1; count += 1; } return 1 << count; } // Driver Code int main() { unsigned int n = 0; printf("%d", nextPowerOf2(n)); return 0; }
Java
// Java program to find // smallest power of 2 // greater than or equal to n import java.io.*; class GFG { static int nextPowerOf2(int n) { int count = 0; // First n in the below // condition is for the // case where n is 0 if (n > 0 && (n & (n - 1)) == 0) return n; while(n != 0) { n >>= 1; count += 1; } return 1 << count; } // Driver Code public static void main(String args[]) { int n = 0; System.out.println(nextPowerOf2(n)); } } // This article is contributed // by Anshika Goyal.
Python3
def nextPowerOf2(n): count = 0 # First n in the below # condition is for the # case where n is 0 if (n and not(n & (n - 1))): return n while( n != 0): n >>= 1 count += 1 return 1 << count # Driver Code n = 0 print(nextPowerOf2(n)) # This code is contributed # by Smitha Dinesh Semwal
C#
// C# program to find smallest // power of 2 greater than // or equal to n using System; class GFG { static int nextPowerOf2(int n) { int count = 0; // First n in the below // condition is for the // case where n is 0 if (n > 0 && (n & (n - 1)) == 0) return n; while(n != 0) { n >>= 1; count += 1; } return 1 << count; } // Driver Code public static void Main() { int n = 0; Console.WriteLine(nextPowerOf2(n)); } } // This code is contributed by anuj_67.
PHP
<?php // PHP program to find smallest // power of 2 greater than or // equal to n function nextPowerOf2($n) { $count = 0; // First n in the below condition // is for the case where n is 0 if ($n && !($n&($n - 1))) return $n; while($n != 0) { $n >>= 1; $count += 1; } return 1 << $count; } // Driver Code $n = 0; echo (nextPowerOf2($n)); // This code is contributed by vt_m ?>
Javascript
<script> // JavaScript program to find // smallest power of 2 // greater than or equal to n function nextPowerOf2(n) { var count = 0; // First n in the below condition // is for the case where n is 0 if (n && !(n & (n - 1))) return n; while( n != 0) { n >>= 1; count += 1; } return 1 << count; } // Driver Code var n = 0; document.write(nextPowerOf2(n)); </script>
1
Complejidad temporal: O(log n)
Espacio auxiliar: O(1)
Método 3 (Cambie el resultado uno por uno)
Gracias a coderyogi por sugerir este método. Este método es una variación del método 2 donde, en lugar de contar, cambiamos el resultado uno por uno en un bucle.
C++
// C++ program to find smallest // power of 2 greater than or // equal to n #include<bits/stdc++.h> using namespace std; unsigned int nextPowerOf2(unsigned int n) { unsigned int p = 1; if (n && !(n & (n - 1))) return n; while (p < n) p <<= 1; return p; } // Driver Code int main() { unsigned int n = 5; cout << nextPowerOf2(n); return 0; } // This code is contributed by rathbhupendra
C
#include<stdio.h> unsigned int nextPowerOf2(unsigned int n) { unsigned int p = 1; if (n && !(n & (n - 1))) return n; while (p < n) p <<= 1; return p; } // Driver Code int main() { unsigned int n = 5; printf("%d", nextPowerOf2(n)); return 0; }
Java
// Java program to find smallest // power of 2 greater than or // equal to n import java.io.*; class GFG { static int nextPowerOf2(int n) { int p = 1; if (n > 0 && (n & (n - 1)) == 0) return n; while (p < n) p <<= 1; return p; } // Driver Code public static void main(String args[]) { int n = 5; System.out.println(nextPowerOf2(n)); } } // This article is contributed // by Anshika Goyal.
Python3
def nextPowerOf2(n): p = 1 if (n and not(n & (n - 1))): return n while (p < n) : p <<= 1 return p; # Driver Code n = 5 print(nextPowerOf2(n)); # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to find smallest // power of 2 greater than or // equal to n using System; class GFG { static int nextPowerOf2(int n) { int p = 1; if (n > 0 && (n & (n - 1)) == 0) return n; while (p < n) p <<= 1; return p; } // Driver Code public static void Main() { int n = 5; Console.Write(nextPowerOf2(n)); } } // This code is contributed by Smitha.
PHP
<?php function nextPowerOf2($n) { $p = 1; if ($n && !($n & ($n - 1))) return $n; while ($p < $n) $p <<= 1; return $p; } // Driver Code $n = 5; echo ( nextPowerOf2($n)); // This code is contributed by vt_m. ?>
Javascript
<script> // Program to find smallest // power of 2 greater than or // equal to n function nextPowerOf2( n) { p = 1; if (n && !(n & (n - 1))) return n; while (p < n) p <<= 1; return p; } // Driver Code n = 5; document.write (nextPowerOf2(n)); //This code is contributed by simranarora5sos </script>
8
Complejidad de tiempo: O(log(n))
Espacio auxiliar: O(1)
Método 4 (Personalizado y Rápido)
1. Subtract n by 1 n = n -1 2. Set all bits after the leftmost set bit. /* Below solution works only if integer is 32 bits */ n = n | (n >> 1); n = n | (n >> 2); n = n | (n >> 4); n = n | (n >> 8); n = n | (n >> 16); 3. Return n + 1
Ejemplo :
Steps 1 & 3 of above algorithm are to handle cases of power of 2 numbers e.g., 1, 2, 4, 8, 16, Let us try for 17(10001) step 1 n = n - 1 = 16 (10000) step 2 n = n | n >> 1 n = 10000 | 01000 n = 11000 n = n | n >> 2 n = 11000 | 00110 n = 11110 n = n | n >> 4 n = 11110 | 00001 n = 11111 n = n | n >> 8 n = 11111 | 00000 n = 11111 n = n | n >> 16 n = 11110 | 00000 n = 11111 step 3: Return n+1 We get n + 1 as 100000 (32)
Programa:
C++
// C++ program to // Finds next power of two // for n. If n itself is a // power of two then returns n #include <bits/stdc++.h> using namespace std; unsigned int nextPowerOf2(unsigned int n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; } // Driver Code int main() { unsigned int n = 5; cout << nextPowerOf2(n); return 0; } // This code is contributed by SHUBHAMSINGH10
C
#include <stdio.h> // Finds next power of two // for n. If n itself is a // power of two then returns n unsigned int nextPowerOf2(unsigned int n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; } // Driver Code int main() { unsigned int n = 5; printf("%d", nextPowerOf2(n)); return 0; }
Java
// Java program to find smallest // power of 2 greater than or // equal to n import java.io.*; class GFG { // Finds next power of two // for n. If n itself is a // power of two then returns n static int nextPowerOf2(int n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; } // Driver Code public static void main(String args[]) { int n = 5; System.out.println(nextPowerOf2(n)); } } // This article is contributed // by Anshika Goyal.
Python3
# Finds next power of two # for n. If n itself is a # power of two then returns n def nextPowerOf2(n): n -= 1 n |= n >> 1 n |= n >> 2 n |= n >> 4 n |= n >> 8 n |= n >> 16 n += 1 return n # Driver program to test # above function n = 5 print(nextPowerOf2(n)) # This code is contributed # by Smitha
C#
// C# program to find smallest // power of 2 greater than or // equal to n using System; class GFG { // Finds next power of two // for n. If n itself is a // power of two then returns n static int nextPowerOf2(int n) { n--; n |= n >> 1; n |= n >> 2; n |= n >> 4; n |= n >> 8; n |= n >> 16; n++; return n; } // Driver Code public static void Main() { int n = 5; Console.WriteLine(nextPowerOf2(n)); } } // This code is contributed by anuj_67.
PHP
<?php // PHP program to find smallest // power of 2 greater than or // equal to n // Finds next power of // two for n. If n itself // is a power of two then // returns n function nextPowerOf2($n) { $n--; $n |= $n >> 1; $n |= $n >> 2; $n |= $n >> 4; $n |= $n >> 8; $n |= $n >> 16; $n++; return $n; } // Driver Code $n = 5; echo nextPowerOf2($n); // This code contributed by Ajit ?>
Javascript
<script> // Javascript program to find smallest // power of 2 greater than or // equal to n // Finds next power of // two for n. If n itself // is a power of two then // returns n function nextPowerOf2(n) { n -= 1 n |= n >> 1 n |= n >> 2 n |= n >> 4 n |= n >> 8 n |= n >> 16 n += 1 return n } // Driver Code n = 5; document.write (nextPowerOf2(n)); // This code is contributed by bunnyram19 </script>
8
Complejidad de tiempo: O(log(n))
Espacio auxiliar: O(1)
Enfoque eficiente:
si el número dado es la potencia de dos, entonces es el número requerido; de lo contrario, configure solo el bit izquierdo del bit más significativo que nos da el número requerido.
C++
// C++ program to find // smallest power of 2 // greater than or equal to n #include <iostream> using namespace std; long long nextPowerOf2(long long N) { // if N is a power of two simply return it if (!(N & (N - 1))) return N; // else set only the left bit of most significant bit return 0x8000000000000000 >> (__builtin_clzll(N) - 1); } // Driver Code int main() { long long n = 5; cout << nextPowerOf2(n); return 0; } // This code is contributed by Kasina Dheeraj.
C
// C program to find // smallest power of 2 // greater than or equal to n #include <stdio.h> long long nextPowerOf2(long long N) { // if N is a power of two simply return it if (!(N & (N - 1))) return N; // else set only the left bit of most significant bit return 0x8000000000000000 >> (__builtin_clzll(N) - 1); } // Driver Code int main() { long long n = 5; printf("%lld", nextPowerOf2(n)); return 0; } // This code is contributed by Kasina Dheeraj.
Java
// Java program to find // smallest power of 2 // greater than or equal to n import java.io.*; class GFG { static long nextPowerOf2(long N) { // if N is a power of two simply return it if ((N & (N - 1)) == 0) return N; // else set only the left bit of most significant // bit as in Java right shift is filled with most // significant bit we consider return 0x4000000000000000L >> (Long.numberOfLeadingZeros(N) - 2); } // Driver Code public static void main(String args[]) { long n = 5; System.out.println(nextPowerOf2(n)); } } // This code is contributed // by Kasina Dheeraj.
Python3
# Python program to find # smallest power of 2 # greater than or equal to n #include <iostream> def nextPowerOf2(N): # if N is a power of two simply return it if not (N & (N - 1)): return N # else set only the left bit of most significant bit return int("1" + (len(bin(N)) - 2) * "0", 2) # Driver Code n = 5 print(nextPowerOf2(n)) # this code is contributed by phasing17
C#
// C# program to find // smallest power of 2 // greater than or equal to n using System; using System.Linq; class GFG { static int nextPowerOf2(int N) { // if N is a power of two simply return it if ((N & (N - 1)) == 0) return N; // else set only the left bit of most significant // bit return Convert.ToInt32( "1" + new string('0', Convert.ToString(N, 2).Length), 2); } // Driver Code public static void Main(string[] args) { int n = 5; // Function call Console.WriteLine(nextPowerOf2(n)); } } // This code is contributed // by phasing17
Javascript
// JavaScript program to find // smallest power of 2 // greater than or equal to n function nextPowerOf2(N) { // if N is a power of two simply return it if (!(N & (N - 1))) return N; // else set only the left bit of most significant bit return parseInt("1" + "0".repeat(N.toString(2).length), 2); } // Driver Code let n = 5; console.log(nextPowerOf2(n)); // this code is contributed by phasing17
8
Complejidad de tiempo: O (1) ya que contar ceros a la izquierda puede causar una complejidad de tiempo de O (64) como máximo.
Espacio Auxiliar: O(1)
Publicación relacionada:
potencia más alta de 2 menor o igual que el número dado
Referencias:
http://en.wikipedia.org/wiki/Power_of_2
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