Skip to main content

Check if number is power of 2

The problem of checking whether a given number is a power of two is a common coding task. A number is said to be a power of two if it can be expressed as 2^k, where 'k' is an integer. For example, 2, 4, 8, 16, 32, etc., are all powers of two. Numbers that are not powers of two cannot be expressed as a product of 2 raised to an integer exponent, such as 3, 5, 7, 10, etc.

Explanation with Suitable Example

Let's take a number, say 16, and see how we can determine if it's a power of two. We start with the number 1 (2^0) and keep multiplying it by 2 until we either get the number we're looking for (16 in this case) or a number greater than the target. In this example, the sequence would be 1, 2, 4, 8, 16. Since we have found 16 in the sequence, we can conclude that it's a power of two.

Standard Pseudocode and Algorithm

  1. Create a function is_power_of_two that takes an integer number as input and returns a boolean value (true if the number is a power of two, false otherwise).

  2. Initialize a variable counter to 0 and a boolean variable status to false.

  3. Run a loop while status is false and (2^counter) is less than or equal to the given number.

  4. Inside the loop, check if (2^counter) is equal to the given number. If it is, set status to true.

  5. Increment the counter by 1 in each iteration.

  6. After the loop, if status is false, it means the given number is not a power of two, so print an appropriate message. Otherwise, print that it's a power of two.

Pseudocode

FUNCTION is_power_of_two(number)
    counter = 0
    status = false

    WHILE status == false AND (2^counter) <= number DO
        IF (2^counter) == number THEN
            status = true
        END IF
        counter = counter + 1
    END WHILE

    IF status == false THEN
        PRINT number, "Is not a power of two"
    ELSE
        PRINT number, "Is a power of two"
    END IF
END FUNCTION

Code Solution

Here given code implementation process.

//C Program
//Check if number is power of 2
#include <stdio.h>

//Detect that given number are part of power of 2 or not
void is_power_two(int number)
{
  int status = 0;
  
  int counter =1;

  while(status==0 && (2 << counter) <=number)
  {

    if((2 << counter)==number)
    {
      //When result are exist in power of 2
      status=1;
    } 
    counter++;
  }
  
  if(status==0)
  {
    printf("%d Is not a power of two\n",number);
  }
  else
  {
    printf("%d Is a power of two\n",number);
  }

}
int main()
{
  //Test Cases
  is_power_two(4);
  is_power_two(7);
  is_power_two(32);
  is_power_two(63);
  is_power_two(128);
  return 0;
}

Output

4 Is a power of two
7 Is not a power of two
32 Is a power of two
63 Is not a power of two
128 Is a power of two
/*
  C++ Program
  Check if given number is stable or unstable 
*/
#include<iostream>

using namespace std;
class MyNumber
{
	public:
		//Detect that given number are part of power of 2 or not
		void is_power_two(int number)
		{
			bool status = false;
			int counter = 1;
			while (status == false && (2 << counter) <= number)
			{
				if ((2 << counter) == number)
				{
					//When result are exist in power of 2
					status = true;
				}
				counter++;
			}
			if (status == false)
			{
				cout << "" << number << " Is not a power of two\n";
			}
			else
			{
				cout << "" << number << " Is a power of two\n";
			}
		}
};
int main()
{
	MyNumber obj =  MyNumber();
	//Test Cases
	obj.is_power_two(4);
	obj.is_power_two(7);
	obj.is_power_two(32);
	obj.is_power_two(63);
	obj.is_power_two(128);
	return 0;
}

Output

4 Is a power of two
7 Is not a power of two
32 Is a power of two
63 Is not a power of two
128 Is a power of two
/*
  Java Program
  Check if number is power of 2
*/
public class MyNumber 
{
  //Detect that given number are part of power of 2 or not
  public void is_power_two(int number)
  {
    boolean status = false;
    int counter = 1;
    while (status == false && (2 << counter) <= number)
    {
      if ((2 << counter) == number)
      {
        //When result are exist in power of 2
        status = true;
      }
      counter++;
    }
    if (status == false)
    {
      System.out.print(""+number+" Is not a power of two\n" );
    }
    else
    {
      System.out.print(""+number+" Is a power of two\n");
    }
  }
  public static void main(String[] args) 
  {
    MyNumber obj = new MyNumber();

    //Test Cases
    obj.is_power_two(4);
    obj.is_power_two(7);
    obj.is_power_two(32);
    obj.is_power_two(63);
    obj.is_power_two(128);
  }

}

Output

 4  Is a power of two
 7  Is not a power of two
 32  Is a power of two
 63  Is not a power of two
 128  Is a power of two
/*
  C# Program
  Check if given number is stable or unstable 
*/
using System;
public class MyNumber
{
	//Detect that given number are part of power of 2 or not
	public void is_power_two(int number)
	{
		Boolean status = false;
		int counter = 1;
		while (status == false && (2 << counter) <= number)
		{
			if ((2 << counter) == number)
			{
				//When result are exist in power of 2
				status = true;
			}
			counter++;
		}
		if (status == false)
		{
			Console.Write("" + number + " Is not a power of two\n");
		}
		else
		{
			Console.Write("" + number + " Is a power of two\n");
		}
	}
	public static void Main(String[] args)
	{
		MyNumber obj = new MyNumber();
		//Test Cases
		obj.is_power_two(4);
		obj.is_power_two(7);
		obj.is_power_two(32);
		obj.is_power_two(63);
		obj.is_power_two(128);
	}
}

Output

4 Is a power of two
7 Is not a power of two
32 Is a power of two
63 Is not a power of two
128 Is a power of two
<?php
/*
  Php Program
  Check if given number is stable or unstable 
*/
class MyNumber
{
	//Detect that given number are part of power of 2 or not
	public 	function is_power_two($number)
	{
		$status = false;
		$counter = 1;
		while ($status == false && (2 << $counter) <= $number)
		{
			if ((2 << $counter) == $number)
			{
				//When result are exist in power of 2
				$status = true;
			}
			$counter++;
		}
		if ($status == false)
		{
			echo("". $number ." Is not a power of two\n");
		}
		else
		{
			echo("". $number ." Is a power of two\n");
		}
	}
}

function main()
{
	$obj = new MyNumber();
	//Test Cases
	$obj->is_power_two(4);
	$obj->is_power_two(7);
	$obj->is_power_two(32);
	$obj->is_power_two(63);
	$obj->is_power_two(128);
}
main();

Output

4 Is a power of two
7 Is not a power of two
32 Is a power of two
63 Is not a power of two
128 Is a power of two
/*
  Node Js Program
  Check if given number is stable or unstable 
*/
class MyNumber
{
	//Detect that given number are part of power of 2 or not
	is_power_two(number)
	{
		var status = false;
		var counter = 1;
		while (status == false && (2 << counter) <= number)
		{
			if ((2 << counter) == number)
			{
				//When result are exist in power of 2
				status = true;
			}
			counter++;
		}
		if (status == false)
		{
			process.stdout.write("" + number + " Is not a power of two\n");
		}
		else
		{
			process.stdout.write("" + number + " Is a power of two\n");
		}
	}
}

function main(args)
{
	var obj = new MyNumber();
	//Test Cases
	obj.is_power_two(4);
	obj.is_power_two(7);
	obj.is_power_two(32);
	obj.is_power_two(63);
	obj.is_power_two(128);
}
main();

Output

4 Is a power of two
7 Is not a power of two
32 Is a power of two
63 Is not a power of two
128 Is a power of two
#   Python 3 Program
#   Check if given number is stable or unstable 

class MyNumber :
	# Detect that given number are part of power of 2 or not
	def is_power_two(self, number) :
		status = False
		counter = 1
		while (status == False and(2 << counter) <= number) :
			if ((2 << counter) == number) :
				# When result are exist in power of 2
				status = True
			
			counter += 1
		
		if (status == False) :
			print("", number ," Is not a power of two\n", end = "")
		else :
			print("", number ," Is a power of two\n", end = "")
		
	

def main() :
	obj = MyNumber()
	# Test Cases
	obj.is_power_two(4)
	obj.is_power_two(7)
	obj.is_power_two(32)
	obj.is_power_two(63)
	obj.is_power_two(128)


if __name__ == "__main__": main()

Output

 4  Is a power of two
 7  Is not a power of two
 32  Is a power of two
 63  Is not a power of two
 128  Is a power of two
#   Ruby Program
#   Check if given number is stable or unstable 

class MyNumber

	# Detect that given number are part of power of 2 or not
	def is_power_two(number)
	
		status = false
		counter = 1
		while (status == false && (2 << counter) <= number)
		
			if ((2 << counter) == number)
			
				# When result are exist in power of 2
				status = true
			end
			counter += 1
		end
		if (status == false)
		
			print("", number ," Is not a power of two\n")
		else
		
			print("", number ," Is a power of two\n")
		end
	end
end
def main()

	obj = MyNumber.new()
	# Test Cases
	obj.is_power_two(4)
	obj.is_power_two(7)
	obj.is_power_two(32)
	obj.is_power_two(63)
	obj.is_power_two(128)
end
main()

Output

4 Is a power of two
7 Is not a power of two
32 Is a power of two
63 Is not a power of two
128 Is a power of two

/*
  Scala Program
  Check if given number is stable or unstable 
*/
class MyNumber
{
	//Detect that given number are part of power of 2 or not
	def is_power_two(number: Int): Unit = {
		var status: Boolean = false;
		var counter: Int = 1;
		while (status == false && (2 << counter) <= number)
		{
			if ((2 << counter) == number)
			{
				//When result are exist in power of 2
				status = true;
			}
			counter += 1;
		}
		if (status == false)
		{
			print("" + number + " Is not a power of two\n");
		}
		else
		{
			print("" + number + " Is a power of two\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyNumber = new MyNumber();
		//Test Cases
		obj.is_power_two(4);
		obj.is_power_two(7);
		obj.is_power_two(32);
		obj.is_power_two(63);
		obj.is_power_two(128);
	}
}

Output

4 Is a power of two
7 Is not a power of two
32 Is a power of two
63 Is not a power of two
128 Is a power of two
/*
  Swift Program
  Check if given number is stable or unstable 
*/
class MyNumber
{
	//Detect that given number are part of power of 2 or not
	func is_power_two(_ number: Int)
	{
		var status: Bool = false;
		var counter: Int = 1;
		while (status == false && (2 << counter) <= number)
		{
			if ((2 << counter) == number)
			{
				//When result are exist in power of 2
				status = true;
			}
			counter += 1;
		}
		if (status == false)
		{
			print("", number ," Is not a power of two\n", terminator: "");
		}
		else
		{
			print("", number ," Is a power of two\n", terminator: "");
		}
	}
}
func main()
{
	let obj: MyNumber = MyNumber();
	//Test Cases
	obj.is_power_two(4);
	obj.is_power_two(7);
	obj.is_power_two(32);
	obj.is_power_two(63);
	obj.is_power_two(128);
}
main();

Output

 4  Is a power of two
 7  Is not a power of two
 32  Is a power of two
 63  Is not a power of two
 128  Is a power of two

Resultant Output Explanation

Let's apply the provided code to the test cases:

  1. is_power_two(4): The loop will run for counter values 0, 1, 2, and 3. At counter = 2, (2^2) = 4, which matches the given number. So, the output will be "4 Is a power of two".

  2. is_power_two(7): The loop will run for counter values 0, 1, and 2. At counter = 2, (2^2) = 4, which is less than the given number. So, the loop will terminate, and the output will be "7 Is not a power of two".

  3. is_power_two(32): The loop will run for counter values 0, 1, 2, 3, 4, and 5. At counter = 5, (2^5) = 32, which matches the given number. So, the output will be "32 Is a power of two".

  4. is_power_two(63): The loop will run for counter values 0, 1, 2, 3, 4, and 5. At counter = 5, (2^5) = 32, which is less than the given number. So, the loop will terminate, and the output will be "63 Is not a power of two".

  5. is_power_two(128): The loop will run for counter values 0, 1, 2, 3, 4, 5, 6, and 7. At counter = 7, (2^7) = 128, which matches the given number. So, the output will be "128 Is a power of two".

Time Complexity of the Code

The time complexity of the provided code can be analyzed based on the while loop. In the worst-case scenario, the loop runs until (2^counter) becomes greater than the given number. For any positive integer number, the loop will run until counter reaches the value such that (2^counter) > number.

Let n be the value of the given number. To find the value of counter at which the loop stops, we solve for counter in the equation (2^counter) = number:

2^counter = number Taking logarithms on both sides, log2(2^counter) = log2(number) counter = log2(number)

Therefore, the loop runs log2(n) times in the worst-case scenario. Hence, the time complexity of the code is O(log n).

Finally

The given code provides a simple approach to check if a given number is a power of two. It uses a loop that runs until (2^counter) becomes greater than the given number and checks if the number is found in the sequence of powers of two. The time complexity of the code is O(log n), which makes it efficient for large inputs. The code can be used in various applications where the power of two detection is required, such as in bit manipulation and certain mathematical algorithms.

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