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
-
Create a function
is_power_of_two
that takes an integernumber
as input and returns a boolean value (true if the number is a power of two, false otherwise). -
Initialize a variable
counter
to 0 and a boolean variablestatus
to false. -
Run a loop while
status
is false and (2^counter
) is less than or equal to the givennumber
. -
Inside the loop, check if (2^
counter
) is equal to the givennumber
. If it is, setstatus
to true. -
Increment the
counter
by 1 in each iteration. -
After the loop, if
status
is false, it means the givennumber
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:
-
is_power_two(4): The loop will run for
counter
values 0, 1, 2, and 3. Atcounter
= 2, (2^2) = 4, which matches the givennumber
. So, the output will be "4 Is a power of two". -
is_power_two(7): The loop will run for
counter
values 0, 1, and 2. Atcounter
= 2, (2^2) = 4, which is less than the givennumber
. So, the loop will terminate, and the output will be "7 Is not a power of two". -
is_power_two(32): The loop will run for
counter
values 0, 1, 2, 3, 4, and 5. Atcounter
= 5, (2^5) = 32, which matches the givennumber
. So, the output will be "32 Is a power of two". -
is_power_two(63): The loop will run for
counter
values 0, 1, 2, 3, 4, and 5. Atcounter
= 5, (2^5) = 32, which is less than the givennumber
. So, the loop will terminate, and the output will be "63 Is not a power of two". -
is_power_two(128): The loop will run for
counter
values 0, 1, 2, 3, 4, 5, 6, and 7. Atcounter
= 7, (2^7) = 128, which matches the givennumber
. 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.
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