Posted on by Kalkicode
Code Bit Logic

# Highest power of 2 greater than or equal to given number

The problem at hand is to find the highest power of 2 that is greater than or equal to a given number. In other words, we want to find the smallest power of 2 that is not less than the given number. For example, if the given number is 7, the highest power of 2 greater than or equal to 7 is 8, as 2^3 = 8.

## Explanation with Suitable Example

Let's take a few examples to understand the problem better:

1. Given number: 7 Highest power of 2 greater than or equal to 7: 8 (2^3 = 8)

2. Given number: 17 Highest power of 2 greater than or equal to 17: 32 (2^5 = 32)

3. Given number: 13 Highest power of 2 greater than or equal to 13: 16 (2^4 = 16)

4. Given number: 1 Highest power of 2 greater than or equal to 1: 1 (2^0 = 1)

5. Given number: 64 Highest power of 2 greater than or equal to 64: 64 (2^6 = 64)

## Pseudocode

``````function highestPower(num):
set all bits to the left of the most significant bit in num
result = the number obtained by setting all bits to the left of the most significant bit in (num - 1)
return (result + 1)
``````

## Algorithm Explanation

1. We need to find the highest power of 2 that is greater than or equal to the given number 'num'.
2. To do this, we first set all bits to the left of the most significant bit in 'num'. This effectively sets all bits to the right of the most significant bit to 1.
3. Then, we subtract 1 from 'num' and again set all bits to the left of the most significant bit in the result obtained after subtraction.
4. Finally, we add 1 to this new result, and the value we obtain will be the highest power of 2 greater than or equal to the given number 'num'.

## Code Solution

Here given code implementation process.

``````// Highest power of 2 greater than or equal to given number
#include <stdio.h>

// Actives all bits to the left of most significant bit
int setActive(int num)
{
num = num >> 1 | num;
num = num >> 2 | num;
num = num >> 4 | num;
num = num >> 8 | num;
num = num >> 16 | num;
return num;
}
// Handles the request to find higher or equal power of 2
void highestPower(int num)
{
printf("\n Given number : %d", num);
int result = setActive(num - 1) + 1;
printf("\n Result : %d\n", result);
}
int main(int argc, char const *argv[])
{
// Test Case
highestPower(7);
highestPower(17);
highestPower(13);
highestPower(1);
highestPower(64);
return 0;
}``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````
``````// Java program
// Highest power of 2 greater than or equal to given number
public class Power
{
// Actives all bits to the left of most significant bit
public int setActive(int num)
{
num = num >> 1 | num;
num = num >> 2 | num;
num = num >> 4 | num;
num = num >> 8 | num;
num = num >> 16 | num;
return num;
}
// Handles the request to find higher or equal power of 2
public void highestPower(int num)
{
System.out.print("\n Given number : " + num);
int result = setActive(num - 1) + 1;
System.out.print("\n Result : " + result + "\n");
}
public static void main(String[] args)
{
// Test Case
}
}``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````
``````// Include header file
#include <iostream>
using namespace std;

// C++ program
// Highest power of 2 greater than or equal to given number

class Power
{
public:
// Actives all bits to the left of most significant bit
int setActive(int num)
{
num = num >> 1 | num;
num = num >> 2 | num;
num = num >> 4 | num;
num = num >> 8 | num;
num = num >> 16 | num;
return num;
}
// Handles the request to find higher or equal power of 2
void highestPower(int num)
{
cout << "\n Given number : " << num;
int result = this->setActive(num - 1) + 1;
cout << "\n Result : " << result << "\n";
}
};
int main()
{
// Test Case
return 0;
}``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````
``````// Include namespace system
using System;
// C# program
// Highest power of 2 greater than or equal to given number
public class Power
{
// Actives all bits to the left of most significant bit
public int setActive(int num)
{
num = num >> 1 | num;
num = num >> 2 | num;
num = num >> 4 | num;
num = num >> 8 | num;
num = num >> 16 | num;
return num;
}
// Handles the request to find higher or equal power of 2
public void highestPower(int num)
{
Console.Write("\n Given number : " + num);
int result = setActive(num - 1) + 1;
Console.Write("\n Result : " + result + "\n");
}
public static void Main(String[] args)
{
// Test Case
}
}``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````
``````<?php
// Php program
// Highest power of 2 greater than or equal to given number
class Power
{
// Actives all bits to the left of most significant bit
public	function setActive(\$num)
{
\$num = \$num >> 1 | \$num;
\$num = \$num >> 2 | \$num;
\$num = \$num >> 4 | \$num;
\$num = \$num >> 8 | \$num;
\$num = \$num >> 16 | \$num;
return \$num;
}
// Handles the request to find higher or equal power of 2
public	function highestPower(\$num)
{
echo "\n Given number : ". \$num;
\$result = \$this->setActive(\$num - 1) + 1;
echo "\n Result : ". \$result ."\n";
}
}

function main()
{
}
main();``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````
``````// Node Js program
// Highest power of 2 greater than or equal to given number
class Power
{
// Actives all bits to the left of most significant bit
setActive(num)
{
num = num >> 1 | num;
num = num >> 2 | num;
num = num >> 4 | num;
num = num >> 8 | num;
num = num >> 16 | num;
return num;
}
// Handles the request to find higher or equal power of 2
highestPower(num)
{
process.stdout.write("\n Given number : " + num);
var result = this.setActive(num - 1) + 1;
process.stdout.write("\n Result : " + result + "\n");
}
}

function main()
{
// Test Case
}
main();``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````
``````#  Python 3 program
#  Highest power of 2 greater than or equal to given number
class Power :
#  Actives all bits to the left of most significant bit
def setActive(self, num) :
num = num >> 1 | num
num = num >> 2 | num
num = num >> 4 | num
num = num >> 8 | num
num = num >> 16 | num
return num

#  Handles the request to find higher or equal power of 2
def highestPower(self, num) :
print("\n Given number : ", num, end = "")
result = self.setActive(num - 1) + 1
print("\n Result : ", result )

def main() :
#  Test Case

if __name__ == "__main__": main()``````

#### Output

`````` Given number :  7
Result :  8

Given number :  17
Result :  32

Given number :  13
Result :  16

Given number :  1
Result :  1

Given number :  64
Result :  64``````
``````#  Ruby program
#  Highest power of 2 greater than or equal to given number
class Power
#  Actives all bits to the left of most significant bit
def setActive(num)
num = num >> 1 | num
num = num >> 2 | num
num = num >> 4 | num
num = num >> 8 | num
num = num >> 16 | num
return num
end

#  Handles the request to find higher or equal power of 2
def highestPower(num)
print("\n Given number : ", num)
result = self.setActive(num - 1) + 1
print("\n Result : ", result ,"\n")
end

end

def main()
#  Test Case
end

main()``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64
``````
``````// Scala program
// Highest power of 2 greater than or equal to given number
class Power
{
// Actives all bits to the left of most significant bit
def setActive(n: Int): Int = {
var num = n;
num = (num >> 1) | num;
num = (num >> 2) | num;
num = (num >> 4) | num;
num = (num >> 8) | num;
num = (num >> 16) | num;
return num;
}
// Handles the request to find higher or equal power of 2
def highestPower(num: Int): Unit = {
print("\n Given number : " + num);
var result: Int = this.setActive(num - 1) + 1;
print("\n Result : " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Power = new Power();
// Test Case
}
}``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````
``````// Swift 4 program
// Highest power of 2 greater than or equal to given number
class Power
{
// Actives all bits to the left of most significant bit
func setActive(_ n: Int)->Int
{
var num = n;
num = (num >> 1) | num;
num = (num >> 2) | num;
num = (num >> 4) | num;
num = (num >> 8) | num;
num = (num >> 16) | num;
return num;
}
// Handles the request to find higher or equal power of 2
func highestPower(_ num: Int)
{
print("\n Given number : ", num, terminator: "");
let result: Int = self.setActive(num - 1) + 1;
print("\n Result : ", result );
}
}
func main()
{
// Test Case
}
main();``````

#### Output

`````` Given number :  7
Result :  8

Given number :  17
Result :  32

Given number :  13
Result :  16

Given number :  1
Result :  1

Given number :  64
Result :  64``````
``````// Kotlin program
// Highest power of 2 greater than or equal to given number
class Power
{
// Actives all bits to the left of most significant bit
fun setActive(n: Int): Int
{
var num = n;
num = (num shr 1) or num;
num = (num shr 2) or num;
num = (num shr 4) or num;
num = (num shr 8) or num;
num = (num shr 16) or num;
return num;
}
// Handles the request to find higher or equal power of 2
fun highestPower(num: Int): Unit
{
print("\n Given number : " + num);
var result: Int = this.setActive(num - 1) + 1;
print("\n Result : " + result + "\n");
}
}
fun main(args: Array < String > ): Unit
{
// Test Case
}``````

#### Output

`````` Given number : 7
Result : 8

Given number : 17
Result : 32

Given number : 13
Result : 16

Given number : 1
Result : 1

Given number : 64
Result : 64``````

## Time Complexity

The time complexity of the provided code is O(1) because the `setActive` function performs a fixed number of bitwise operations, regardless of the value of the input number 'num'. The main function `highestPower` then calls this function and performs a few arithmetic operations, which also take constant time.

## Resultant Output Explanation

The given code provides the output for the test cases mentioned in the main function. Let's analyze the output for each test case:

1. Given number : 7 Result : 8

2. Given number : 17 Result : 32

3. Given number : 13 Result : 16

4. Given number : 1 Result : 1

5. Given number : 64 Result : 64

The output is as expected, and the code successfully finds the highest power of 2 greater than or equal to the given numbers.

## Finally

In this problem, we aimed to find the highest power of 2 greater than or equal to a given number. By using bitwise operations and arithmetic operations, we efficiently solved the problem with a time complexity of O(1). The provided C code gives correct results for various test cases, and the explanation with suitable examples helps to understand the problem and its solution clearly.

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