Skip to main content

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

Let's start with a standard pseudocode to solve the problem:

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)
	{
		Power task = new Power();
		// Test Case
		task.highestPower(7);
		task.highestPower(17);
		task.highestPower(13);
		task.highestPower(1);
		task.highestPower(64);
	}
}

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()
{
	Power task = Power();
	// Test Case
	task.highestPower(7);
	task.highestPower(17);
	task.highestPower(13);
	task.highestPower(1);
	task.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
// 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)
	{
		Power task = new Power();
		// Test Case
		task.highestPower(7);
		task.highestPower(17);
		task.highestPower(13);
		task.highestPower(1);
		task.highestPower(64);
	}
}

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()
{
	$task = new Power();
	$task->highestPower(7);
	$task->highestPower(17);
	$task->highestPower(13);
	$task->highestPower(1);
	$task->highestPower(64);
}
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()
{
	var task = new Power();
	// Test Case
	task.highestPower(7);
	task.highestPower(17);
	task.highestPower(13);
	task.highestPower(1);
	task.highestPower(64);
}
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() :
	task = Power()
	#  Test Case
	task.highestPower(7)
	task.highestPower(17)
	task.highestPower(13)
	task.highestPower(1)
	task.highestPower(64)

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() 
	task = Power.new()
	#  Test Case
	task.highestPower(7)
	task.highestPower(17)
	task.highestPower(13)
	task.highestPower(1)
	task.highestPower(64)
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
		task.highestPower(7);
		task.highestPower(17);
		task.highestPower(13);
		task.highestPower(1);
		task.highestPower(64);
	}
}

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()
{
	let task: Power = Power();
	// Test Case
	task.highestPower(7);
	task.highestPower(17);
	task.highestPower(13);
	task.highestPower(1);
	task.highestPower(64);
}
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
{
	var task: Power = Power();
	// Test Case
	task.highestPower(7);
	task.highestPower(17);
	task.highestPower(13);
	task.highestPower(1);
	task.highestPower(64);
}

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.

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