Mayor potencia de 2 menor o igual al número dado

Dado un número n, encuentre la mayor potencia de 2 que sea menor o igual que n.

Ejemplos: 

Input : n = 10
Output : 8

Input : n = 19
Output : 16

Input : n = 32
Output : 32

Una solución simple es comenzar a verificar desde n y seguir disminuyendo hasta encontrar una potencia de 2.  

C++

// C++ program to find highest power of 2 smaller
// than or equal to n.
#include <bits/stdc++.h>
using namespace std;
 
int highestPowerof2(int n)
{
    int res = 0;
    for (int i = n; i >= 1; i--) {
        // If i is a power of 2
        if ((i & (i - 1)) == 0) {
            res = i;
            break;
        }
    }
    return res;
}
 
// Driver code
int main()
{
    int n = 10;
    cout << highestPowerof2(n);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

C

// C program to find highest power of 2 smaller
// than or equal to n.
#include <stdio.h>
 
int highestPowerof2(int n)
{
    int res = 0;
    for (int i = n; i >= 1; i--) {
        // If i is a power of 2
        if ((i & (i - 1)) == 0) {
            res = i;
            break;
        }
    }
    return res;
}
 
// Driver code
int main()
{
    int n = 10;
    printf("%d", highestPowerof2(n));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

Java

// Java program to find highest power of
// 2 smaller than or equal to n.
class GFG{
 
static int highestPowerof2(int n)
{
    int res = 0;
    for(int i = n; i >= 1; i--)
    {
         
        // If i is a power of 2
        if ((i & (i-1)) == 0)
        {
            res = i;
            break;
        }
    }
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 10;
     
    System.out.print(highestPowerof2(n));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find highest
# power of 2 smaller than or
# equal to n.
def highestPowerof2(n):
 
    res = 0;
    for i in range(n, 0, -1):
         
        # If i is a power of 2
        if ((i & (i - 1)) == 0):
         
            res = i;
            break;
         
    return res;
 
# Driver code
n = 10;
print(highestPowerof2(n));
     
# This code is contributed by mits

C#

// C# code to find highest power
// of 2 smaller than or equal to n.
using System;
 
class GFG
{
public static int highestPowerof2(int n)
{
    int res = 0;
    for (int i = n; i >= 1; i--)
        {
        // If i is a power of 2
        if ((i & (i - 1)) == 0)
            {
                res = i;
                break;
            }
        }
    return res;
}
     
    // Driver Code
    static public void Main ()
    {
        int n = 10;
        Console.WriteLine(highestPowerof2(n));
    }
}
 
// This code is contributed by ajit

PHP

<?php
// PHP program to find highest
// power of 2 smaller than or
// equal to n.
function highestPowerof2($n)
{
    $res = 0;
    for ($i = $n; $i >= 1; $i--)
    {
        // If i is a power of 2
        if (($i & ($i - 1)) == 0)
        {
            $res = $i;
            break;
        }
    }
    return $res;
}
 
// Driver code
$n = 10;
echo highestPowerof2($n);
     
// This code is contributed by m_kit
?>

Javascript

<script>
 
// JavaScript program to find highest power
// of 2 smaller than or equal to n.
 
   function highestPowerof2(n)
   {
     let res = 0;
     for (let i = n; i >= 1; i--)
        {
         // If i is a power of 2
          if ((i & (i - 1)) == 0)
             {
                  res = i;
                break;
             }
        }
     return res;
   }
   
 
// Driver code
      let n = 10;
      document.write(highestPowerof2(n));
   
</script>
Producción

8

Complejidad temporal : O(n). En el peor de los casos, el ciclo se ejecuta piso(n/2) veces. El peor caso ocurre cuando n es de la forma 2 x – 1.

Espacio auxiliar : O (1) ya que solo se usa espacio constante para variables

Una solución eficiente es utilizar el operador de desplazamiento a la izquierda bit a bit para encontrar todas las potencias de 2 a partir de 1. Para cada potencia, compruebe si es menor o igual que n o no. A continuación se muestra la implementación de la idea.

C++

// C++ program to find highest power of 2 smaller
// than or equal to n.
#include <bits/stdc++.h>
using namespace std;
 
int highestPowerof2(unsigned int n)
{
    // Invalid input
    if (n < 1)
        return 0;
    int res = 1;
    // Try all powers starting from 2^1
    for (int i = 0; i < 8 * sizeof(unsigned int); i++) {
        int curr = 1 << i;
        // If current power is more than n, break
        if (curr > n)
            break;
        res = curr;
    }
    return res;
}
 
// Driver code
int main()
{
    int n = 10;
    cout << highestPowerof2(n);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

C

// C program to find highest power of 2 smaller
// than or equal to n.
#include <stdio.h>
 
int highestPowerof2(unsigned int n)
{
    // Invalid input
    if (n < 1)
        return 0;
    int res = 1;
    // Try all powers starting from 2^1
    for (int i = 0; i < 8 * sizeof(unsigned int); i++) {
        int curr = 1 << i;
        // If current power is more than n, break
        if (curr > n)
            break;
        res = curr;
    }
    return res;
}
 
// Driver code
int main()
{
    int n = 10;
    printf("%d", highestPowerof2(n));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

Java

// Java program to find
// highest power of 2 smaller
// than or equal to n.
import java.io.*;
 
class GFG
{
static int highestPowerof2(int n)
{
    // Invalid input
    if (n < 1)
        return 0;
 
    int res = 1;
 
    // Try all powers
    // starting from 2^1
    for (int i = 0; i < 8 * Integer.BYTES; i++)
    {
        int curr = 1 << i;
 
        // If current power is
        // more than n, break
        if (curr > n)
        break;
 
        res = curr;
    }
 
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 10;
    System.out.println(highestPowerof2(n));
}
}
 
// This code is contributed aj_36

python3

# Python3 program to find highest power of 2 smaller
# than or equal to n.
 
import sys
 
def highestPowerof2( n):
 
    # Invalid input
    if (n < 1):
        return 0
  
    res = 1
  
    #Try all powers starting from 2^1
    for i in range(8*sys.getsizeof(n)):
     
        curr = 1 << i
  
        # If current power is more than n, break
        if (curr > n):
             break
  
        res = curr
  
    return res
  
# Driver code
if __name__ == "__main__":
 
    n = 10
    print(highestPowerof2(n))
   

C#

// C# program to find
// highest power of 2 smaller
// than or equal to n.
using System;
 
class GFG
{
static int highestPowerof2(int n)
{
    // Invalid input
    if (n < 1)
        return 0;
 
    int res = 1;
 
    // Try all powers
    // starting from 2^1
    for (int i = 0; i < 8 * sizeof(uint); i++)
    {
        int curr = 1 << i;
 
        // If current power is
        // more than n, break
        if (curr > n)
        break;
 
        res = curr;
    }
 
    return res;
}
 
// Driver code
static public void Main ()
{
    int n = 10;
    Console.WriteLine(highestPowerof2(n));
}
}
 
// This code is contributed ajit

PHP

<?php
// PHP program to find highest
// power of 2 smaller
// than or equal to n.
 
function highestPowerof2($n)
{
    // Invalid input
    if ($n < 1)
        return 0;
 
    $res = 1;
 
    // Try all powers starting
    // from 2^1
    for ($i = 0; $i < 8 * PHP_INT_SIZE; $i++)
    {
        $curr = 1 << $i;
 
        // If current power is
        // more than n, break
        if ($curr > $n)
        break;
 
        $res = $curr;
    }
 
    return $res;
}
 
// Driver code
$n = 10;
echo highestPowerof2($n);
     
// This code is contributed
// by m_kit
?>

Javascript

<script>
 
 
function highestPowerof2(n)
{
    // Invalid input
    if (n < 1)
        return 0;
 
    let res = 1;
 
    // Try all powers starting from 2^1
    for (let i=0; i<8; i++)
    {
        let curr = 1 << i;
 
        // If current power is more than n, break
        if (curr > n)
           break;
 
        res = curr;
    }
 
    return res;
}
 
// Driver code
 
let n = 10;
document.write(highestPowerof2(n));
 
</script>
Producción

8

Complejidad del tiempo: O(32)

Espacio Auxiliar: O(1)

Una solución usando Log(n)
Gracias a Anshuman Jha por sugerir esta solución. 

C++

// C++ program to find highest power of 2 smaller
// than or equal to n.
#include<bits/stdc++.h>
using namespace std;
 
int highestPowerof2(int n)
{
   int p = (int)log2(n);
   return (int)pow(2, p);
}
 
// Driver code
int main()
{
    int n = 10;
    cout << highestPowerof2(n);
    return 0;
}

Java

// Java program to find
// highest power of 2
// smaller than or equal to n.
import java.io.*;
 
class GFG
{
static int highestPowerof2(int n)
{
     
    int p = (int)(Math.log(n) /
                  Math.log(2));
    return (int)Math.pow(2, p);
}
 
// Driver code
public static void main (String[] args)
{
    int n = 10;
    System.out.println(highestPowerof2(n));
}
}
 
// This code is contributed
// by m_kit

Python3

# Python3 program to find highest
# power of 2 smaller than or
# equal to n.
import math
 
def highestPowerof2(n):
 
    p = int(math.log(n, 2));
    return int(pow(2, p));
 
# Driver code
n = 10;
print(highestPowerof2(n));
 
# This code is contributed by mits

C#

// C# program to find
// highest power of 2
// smaller than or equal to n.
using System;
 
class GFG
{
static int highestPowerof2(int n)
{
    int p = (int)(Math.Log(n) /
                   Math.Log(2));
    return (int)Math.Pow(2, p);
}
 
// Driver code
static public void Main ()
{
    int n = 10;
    Console.WriteLine(highestPowerof2(n));
}
}
 
// This code is contributed
// by ajit

PHP

<?php
// PHP program to find highest
// power of 2 smaller than or
// equal to n.
function highestPowerof2($n)
{
    $p = (int)log($n, 2);
    return (int)pow(2, $p);
}
 
// Driver code
$n = 10;
echo highestPowerof2($n);
 
// This code is contributed by ajit
?>

Javascript

<script>
    // Javascript program to find
    // highest power of 2
    // smaller than or equal to n.
     
    function highestPowerof2(n)
    {
        let p = parseInt(Math.log(n) / Math.log(2), 10);
        return Math.pow(2, p);
    }
     
    let n = 10;
    document.write(highestPowerof2(n));
     
    // This code is contributed by divyeshrabadiya07.
</script>
Producción

8

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)

Solución usando máscaras de bits:

C++

// C++ program to find highest power of 2 smaller
// than or equal to n.
#include <iostream>
using namespace std;
 
unsigned highestPowerof2(unsigned x)
{
    // check for the set bits
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
 
    // Then we remove all but the top bit by xor'ing the
    // string of 1's with that string of 1's shifted one to
    // the left, and we end up with just the one top bit
    // followed by 0's.
    return x ^ (x >> 1);
}
 
int main()
{
 
    int n = 10;
    cout << highestPowerof2(n) << "\n";
 
    return 0;
}
 
// This code is contributed by Rudrakshi.

Java

// Java program to find highest power of 2 smaller
// than or equal to n.
import java.io.*;
class GFG
{
     
    static int highestPowerof2(int x)
    {
       
        // check for the set bits
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
         
        // Then we remove all but the top bit by xor'ing the
        // string of 1's with that string of 1's shifted one to
        // the left, and we end up with just the one top bit
        // followed by 0's.
        return x ^ (x >> 1); 
     
    }
     
  // Driver code
    public static void main (String[] args)
    {       
        int n = 10;
        System.out.println(highestPowerof2(n));
    }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 program to find highest power of 2 smaller than or equal to n.
 
def highestPowerof2(x):
    # check for the set bits
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
     
    # Then we remove all but the top bit by xor'ing the
    # string of 1's with that string of 1's shifted one to
    # the left, and we end up with just the one top bit
    # followed by 0's.
    return x ^ (x >> 1)
 
n = 10
print(highestPowerof2(n))
 
# This code is contributed by divyesh072019.

C#

// C# program to find highest power of 2 smaller
// than or equal to n.
using System;
public class GFG
{
 
  static int highestPowerof2(int x)
  {
 
    // check for the set bits
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
 
    // Then we remove all but the top bit by xor'ing the
    // string of 1's with that string of 1's shifted one to
    // the left, and we end up with just the one top bit
    // followed by 0's.
    return x ^ (x >> 1); 
 
  }
 
  // Driver code
  public static void Main(String[] args)
  {       
    int n = 10;
    Console.WriteLine(highestPowerof2(n));
  }
}
 
// This code is contributed by umadevi9616

Javascript

<script>
// Javascript program to find highest power of 2 smaller
// than or equal to n.
function highestPowerof2(x)
{
 
    // check for the set bits
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
  
    // Then we remove all but the top bit by xor'ing the
    // string of 1's with that string of 1's shifted one to
    // the left, and we end up with just the one top bit
    // followed by 0's.
    return x ^ (x >> 1);
}
 
let n = 10;
document.write(highestPowerof2(n))
 
// This code is contributed by rag2127
</script>
Producción

8

Complejidad de tiempo: O(1)

Espacio auxiliar : O (1) ya que solo se usa espacio constante para variables

Una solución usando MSB

Si el número dado es la potencia de dos, entonces es el número requerido; de lo contrario, establezca solo el bit más significativo que nos da el número requerido.

C++

// C++ program to find
// smallest power of 2
// smaller than or equal to n
#include <iostream>
using namespace std;
 
long long highestPowerof2(long long N)
{
    // if N is a power of two simply return it
    if (!(N & (N - 1)))
        return N;
    // else set only the most significant bit
    return 0x8000000000000000 >> (__builtin_clzll(N));
}
 
// Driver Code
int main()
{
    long long n = 5;
    cout << highestPowerof2(n);
    return 0;
}
 
// This code is contributed by phasing17
Producción

4

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)

Problema de aplicación: 
Algunas personas están haciendo cola. Un proceso de selección sigue una regla en la que se seleccionan personas que se encuentran en posiciones pares. De las personas seleccionadas se forma una cola y nuevamente de estas solo se seleccionan las personas en posiciones pares. Esto continúa hasta que nos quedamos con una persona. Averigüe la posición de esa persona en la cola original. 
Imprime la posición (cola original) de esa persona que queda. 

Ejemplos: 

Input: n = 10
Output:8
Explanation : 
1 2 3 4 5 6 7 8 9 10  ===>Given queue
    2 4 6 8 10
       4 8
        8

Input: n = 17
Input: 16
Explanation : 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  ===>Given queue
        2 4 6 8 10 12 14 16
            4 8 12 16
              8 16
               16

Artículo relacionado: 
Potencia de 2 mayor o igual a un número dado.
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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

Deja una respuesta

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