Smallest power of 2 greater than or equal to n
Write a function that, for a given no n, finds a number p which is greater than or equal to n and is the smallest power of 2.
Examples :
Input: n = 5
Output: 8Input: n = 17
Output: 32Input : n = 32
Output: 32
Method 1: Using log2(number)
- Calculate the log2(N) and store it into a variable say ‘a’
- Check if pow(2, a) is equals to N
- Return, N
- Otherwise, return pow(2, a + 1)
Below is the implementation of the above approach:
C++
// C++ program to find // smallest power of 2 // greater than or equal to n #include <bits/stdc++.h> using namespace std; long long nearestPowerOf2( long long N) { long long a = log2(N); if ( pow (2, a) == N) return N; return pow (2, a + 1); } // Driver Code int main() { unsigned int n = 5; cout << nearestPowerOf2(n); return 0; } // This code is contributed by hkdass001 |
Java
/*package whatever //do not write package name here */ import java.io.*; public class GFG { public static long nearestPowerOf2( long N) { long a = ( int )(Math.log(N) / Math.log( 2 )); if (Math.pow( 2 , a) == N) return N; return ( long ) Math.pow( 2 , a + 1 ); } // Driver Code public static void main (String[] args) { long n = 5 ; System.out.println(nearestPowerOf2(n)); } } // This code is contributed by Ajax |
Python3
#Python program to find #smallest power of 2 #greater than or equal to n import math # Function to find the smallest power of 2 # greater than or equal to n def nearestPowerOf2(N): # Calculate log2 of N a = int (math.log2(N)) # If 2^a is equal to N, return N if 2 * * a = = N: return N # Return 2^(a + 1) return 2 * * (a + 1 ) # Main function if __name__ = = "__main__" : # Input number n = 5 # Call the nearestPowerOf2 function print (nearestPowerOf2(n)) |
C#
using System; public class GFG { public static long nearestPowerOf2( long N) { long a = ( int )(Math.Log(N) / Math.Log(2)); if (Math.Pow(2, a) == N) return N; return ( long ) Math.Pow(2, a + 1); } // Driver Code public static void Main (String[] args) { long n = 5; Console.WriteLine(nearestPowerOf2(n)); } } // This code contributed by SRJ |
Javascript
// Function to find the smallest power of 2 // greater than or equal to N function nearestPowerOf2(N) { // Calculate log2 of N var a = Math.floor(Math.log2(N)); // If 2^a is equal to N, return N if (Math.pow(2, a) === N) { return N; } // Return 2^(a + 1) return Math.pow(2, a + 1); } // Main function // Input number var n = 5; // Call the nearestPowerOf2 function console.log(nearestPowerOf2(n)); |
8
Time Complexity: O(1)
Auxiliary Space: O(1)
Example :
Let us try for 17 pos = 5 p = 32
Method 2 (By getting the position of only set bit in result )
/* 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)
Example :
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
Time Complexity: O(log n)
Auxiliary Space: O(1)
Method 3(Shift result one by one)
Thanks to coderyogi for suggesting this method . This method is a variation of method 2 where instead of getting count, we shift the result one by one in a loop.
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
Time Complexity: O(log(n))
Auxiliary Space: O(1)
Method 4(Customized and Fast)
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
Example :
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)
Program:
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
Time Complexity : O(log(n))
Auxiliary Space: O(1)
Efficient approach:
If the given number is the power of two then it is the required number otherwise set only the left bit of most significant bit which gives us the required number.
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
Time Complexity : O(1) as counting leading zeroes can cause at most O(64) time complexity.
Auxiliary Space: O(1)
Related Post :
Highest power of 2 less than or equal to given number
References :
http://en.wikipedia.org/wiki/Power_of_2
Contact Us