Posted on by Kalkicode
Code Bit Logic

# 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.

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

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)
{
// Test A
int num = 17;
// Test B
num = 64;
// Test C
num = 15;
}
}``````

#### 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()
{
// Test A
int num = 17;
// Test B
num = 64;
// Test C
num = 15;
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)
{
// Test A
int num = 17;
// Test B
num = 64;
// Test C
num = 15;
}
}``````

#### 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
// Test B
num = 64
// Test C
num = 15
}``````

#### 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()
{
// Test A
\$num = 17;
// Test B
\$num = 64;
// Test C
\$num = 15;
}
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()
{
// Test A
var num = 17;
// Test B
num = 64;
// Test C
num = 15;
}
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() :
#  Test A
num = 17
#  Test B
num = 64
#  Test C
num = 15

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()
#  Test A
num = 17
#  Test B
num = 64
#  Test C
num = 15
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;
// Test B
num = 64;
// Test C
num = 15;
}
}``````

#### 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()
{
// Test A
var num: Int = 17;
// Test B
num = 64;
// Test C
num = 15;
}
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
{
// Test A
var num: Int = 17;
// Test B
num = 64;
// Test C
num = 15;
}``````

#### 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.

## 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.

Categories
Relative Post