Skip to main content

Smallest power of 2 greater than or equal to n

The problem is to find the smallest power of 2 that is greater than or equal to a given positive integer 'n'. We need to devise an algorithm to efficiently compute this value without using the power function. This can be useful in various scenarios, such as determining the appropriate size for data structures or when optimizing algorithms.

Explanation with Example

Let's take the number 'n' as 17, and we need to find the smallest power of 2 greater than or equal to 17.

  1. Start with x = 1, as 2^0 = 1.
  2. In the loop, we repeatedly double the value of x by left-shifting it by one position until x becomes greater than or equal to n.
  3. In each iteration, x takes on the values: 1, 2, 4, 8, 16, 32. When x becomes 32, which is greater than 17, we exit the loop.
  4. The result is 32, which is the smallest power of 2 greater than or equal to 17.

Pseudocode

function findPower2(n):
    x = 1
    while x < n:
        x = x << 1
    return x

Algorithm Explanation

  1. Start with x = 1.
  2. Enter the loop and check if x is less than n.
  3. If it is, double the value of x by left-shifting it one position to the left (x = x << 1).
  4. Repeat step 2 and 3 until x is greater than or equal to n.
  5. Return the value of x, which is the smallest power of 2 greater than or equal to n.

Code Solution

Here given code implementation process.

// C program for
// Smallest power of 2 greater than or equal to n
#include <stdio.h>

void findPower2(int n)
{
	// Start to 1
	int x = 1;
	while (x < n)
	{
		// Shift the value of x value by one to left side
		x = x << 1;
	}
	// Display calculated result
	printf("\n Given n : %d", n);
	printf("\n Result  : %d\n", x);
}
int main()
{
	// Test A
	int num = 17;
	findPower2(num);
	// Test B
	num = 64;
	findPower2(num);
	// Test C
	num = 15;
	findPower2(num);
	return 0;
}

Output

 Given n : 17
 Result  : 32

 Given n : 64
 Result  : 64

 Given n : 15
 Result  : 16
// Java program for
// Smallest power of 2 greater than or equal to n
public class Power
{
	public void findPower2(int n)
	{
		// Start to 1
		int x = 1;
		while (x < n)
		{
			// Shift the value of x value by one to left side
			x = x << 1;
		}
		// Display calculated result
		System.out.print("\n Given n : " + n);
		System.out.print("\n Result : " + x + "\n");
	}
	public static void main(String[] args)
	{
		Power task = new Power();
		// Test A
		int num = 17;
		task.findPower2(num);
		// Test B
		num = 64;
		task.findPower2(num);
		// Test C
		num = 15;
		task.findPower2(num);
	}
}

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Smallest power of 2 greater than or equal to n
class Power
{
	public: void findPower2(int n)
	{
		// Start to 1
		int x = 1;
		while (x < n)
		{
			// Shift the value of x value by one to left side
			x = x << 1;
		}
		// Display calculated result
		cout << "\n Given n : " << n;
		cout << "\n Result : " << x << "\n";
	}
};
int main()
{
	Power *task = new Power();
	// Test A
	int num = 17;
	task->findPower2(num);
	// Test B
	num = 64;
	task->findPower2(num);
	// Test C
	num = 15;
	task->findPower2(num);
	return 0;
}

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16
// Include namespace system
using System;
// Csharp program for
// Smallest power of 2 greater than or equal to n
public class Power
{
	public void findPower2(int n)
	{
		// Start to 1
		int x = 1;
		while (x < n)
		{
			// Shift the value of x value by one to left side
			x = x << 1;
		}
		// Display calculated result
		Console.Write("\n Given n : " + n);
		Console.Write("\n Result : " + x + "\n");
	}
	public static void Main(String[] args)
	{
		Power task = new Power();
		// Test A
		int num = 17;
		task.findPower2(num);
		// Test B
		num = 64;
		task.findPower2(num);
		// Test C
		num = 15;
		task.findPower2(num);
	}
}

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16
package main
import "fmt"
// Go program for
// Smallest power of 2 greater than or equal to n
type Power struct {}
func getPower() * Power {
	var me *Power = &Power {}
	return me
}
func(this Power) findPower2(n int) {
	// Start to 1
	var x int = 1
	for (x < n) {
		// Shift the value of x value by one to left side
		x = x << 1
	}
	// Display calculated result
	fmt.Print("\n Given n : ", n)
	fmt.Print("\n Result : ", x, "\n")
}
func main() {
	var task * Power = getPower()
	// Test A
	var num int = 17
	task.findPower2(num)
	// Test B
	num = 64
	task.findPower2(num)
	// Test C
	num = 15
	task.findPower2(num)
}

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16
<?php
// Php program for
// Smallest power of 2 greater than or equal to n
class Power
{
	public	function findPower2($n)
	{
		// Start to 1
		$x = 1;
		while ($x < $n)
		{
			// Shift the value of x value by one to left side
			$x = $x << 1;
		}
		// Display calculated result
		echo("\n Given n : ".$n);
		echo("\n Result : ".$x."\n");
	}
}

function main()
{
	$task = new Power();
	// Test A
	$num = 17;
	$task->findPower2($num);
	// Test B
	$num = 64;
	$task->findPower2($num);
	// Test C
	$num = 15;
	$task->findPower2($num);
}
main();

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16
// Node JS program for
// Smallest power of 2 greater than or equal to n
class Power
{
	findPower2(n)
	{
		// Start to 1
		var x = 1;
		while (x < n)
		{
			// Shift the value of x value by one to left side
			x = x << 1;
		}
		// Display calculated result
		process.stdout.write("\n Given n : " + n);
		process.stdout.write("\n Result : " + x + "\n");
	}
}

function main()
{
	var task = new Power();
	// Test A
	var num = 17;
	task.findPower2(num);
	// Test B
	num = 64;
	task.findPower2(num);
	// Test C
	num = 15;
	task.findPower2(num);
}
main();

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16
#  Python 3 program for
#  Smallest power of 2 greater than or equal to n
class Power :
	def findPower2(self, n) :
		#  Start to 1
		x = 1
		while (x < n) :
			#  Shift the value of x value by one to left side
			x = x << 1
		
		#  Display calculated result
		print("\n Given n : ", n, end = "")
		print("\n Result : ", x )
	

def main() :
	task = Power()
	#  Test A
	num = 17
	task.findPower2(num)
	#  Test B
	num = 64
	task.findPower2(num)
	#  Test C
	num = 15
	task.findPower2(num)

if __name__ == "__main__": main()

Output

 Given n :  17
 Result :  32

 Given n :  64
 Result :  64

 Given n :  15
 Result :  16
#  Ruby program for
#  Smallest power of 2 greater than or equal to n
class Power 
	def findPower2(n) 
		#  Start to 1
		x = 1
		while (x < n) 
			#  Shift the value of x value by one to left side
			x = x << 1
		end

		#  Display calculated result
		print("\n Given n : ", n)
		print("\n Result : ", x ,"\n")
	end

end

def main() 
	task = Power.new()
	#  Test A
	num = 17
	task.findPower2(num)
	#  Test B
	num = 64
	task.findPower2(num)
	#  Test C
	num = 15
	task.findPower2(num)
end

main()

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16

// Scala program for
// Smallest power of 2 greater than or equal to n
class Power()
{
	def findPower2(n: Int): Unit = {
		// Start to 1
		var x: Int = 1;
		while (x < n)
		{
			// Shift the value of x value by one to left side
			x = x << 1;
		}
		// Display calculated result
		print("\n Given n : " + n);
		print("\n Result : " + x + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Power = new Power();
		// Test A
		var num: Int = 17;
		task.findPower2(num);
		// Test B
		num = 64;
		task.findPower2(num);
		// Test C
		num = 15;
		task.findPower2(num);
	}
}

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16
// Swift 4 program for
// Smallest power of 2 greater than or equal to n
class Power
{
	func findPower2(_ n: Int)
	{
		// Start to 1
		var x: Int = 1;
		while (x < n)
		{
			// Shift the value of x value by one to left side
			x = x << 1;
		}
		// Display calculated result
		print("\n Given n : ", n, terminator: "");
		print("\n Result : ", x );
	}
}
func main()
{
	let task: Power = Power();
	// Test A
	var num: Int = 17;
	task.findPower2(num);
	// Test B
	num = 64;
	task.findPower2(num);
	// Test C
	num = 15;
	task.findPower2(num);
}
main();

Output

 Given n :  17
 Result :  32

 Given n :  64
 Result :  64

 Given n :  15
 Result :  16
// Kotlin program for
// Smallest power of 2 greater than or equal to n
class Power
{
	fun findPower2(n: Int): Unit
	{
		// Start to 1
		var x: Int = 1;
		while (x < n)
		{
			// Shift the value of x value by one to left side
			x = x shl 1;
		}
		// Display calculated result
		print("\n Given n : " + n);
		print("\n Result : " + x + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Power = Power();
	// Test A
	var num: Int = 17;
	task.findPower2(num);
	// Test B
	num = 64;
	task.findPower2(num);
	// Test C
	num = 15;
	task.findPower2(num);
}

Output

 Given n : 17
 Result : 32

 Given n : 64
 Result : 64

 Given n : 15
 Result : 16

Output Explanation

  1. For n = 17, the smallest power of 2 greater than or equal to 17 is 32.
  2. For n = 64, the given number is already a power of 2, so the result is 64 itself.
  3. For n = 15, the smallest power of 2 greater than or equal to 15 is 16.

Time Complexity

The time complexity of this algorithm is O(log n). The loop iterates until x becomes greater than or equal to n. At each iteration, the value of x doubles, which means the number of iterations required to reach n is proportional to log(n) to the base 2. Hence, the time complexity of the findPower2 function is logarithmic.

Conclusion: In this article, we explored the problem of finding the smallest power of 2 greater than or equal to a given positive integer 'n'. We provided a simple algorithm to efficiently calculate the result and demonstrated its application with example cases. The algorithm avoids using the power function and has a time complexity of O(log n), making it an efficient solution for the problem at hand.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment