Check if number is power of 4
The problem is to determine whether a given number is a power of 4 or not. A power of 4 is a number that can be expressed in the form 4^k, where 'k' is a non-negative integer. For example.
- 16 is a power of 4 because .
- 8 is not a power of 4 because it cannot be expressed in the form .
- 40 is not a power of 4 for the same reason.
- 64 is a power of 4 because .
- 1 is a power of 4 because .
Problem Statement
Given an integer 'num', the task is to determine whether 'num' is a power of 4.
Idea to Solve
The method you've implemented uses bit manipulation to determine whether a number is a power of 4. Let's break down the approach:
- If the given number
num
is less than or equal to 0, it cannot be a power of 4, so returnfalse
. - Check if
(num & (num - 1))
is equal to 0. This step checks if 'num' is a power of 2. If it's not, then it can't be a power of 4 either, so returnfalse
. - If 'num' is a power of 2, check if
(num & 0xAAAAAAAA)
is equal to 0. This step is designed to ensure that the only '1' bit in 'num' is at an even position. If this condition is met, then 'num' is a power of 4, so returntrue
.
Pseudocode
function isPowerOfFour(num):
if num <= 0:
return false
if (num & (num - 1)) != 0:
return false
if (num & 0xAAAAAAAA) == 0:
return true
return false
Algorithm Explanation
- If 'num' is non-positive, return
false
since no negative number or zero can be a power of 4. - Check if 'num' is a power of 2 by performing the bitwise AND operation between 'num' and 'num - 1'. If this operation results in 0, it means 'num' is a power of 2.
- Further, check if the bitwise AND operation between 'num' and
0xAAAAAAAA
is 0. This step ensures that the only '1' bit in 'num' is at an even position. If this condition holds, it means 'num' is a power of 4.
Code Solution
/*
Java Program for
Check if number is power of 4
*/
public class Test
{
// Check if that given number is power of 4 or not
public static boolean isPowerOfFour(int num)
{
if (num <= 0)
{
return false;
}
if ((num & (num - 1)) != 0)
{
return false;
}
if ((num & 0xAAAAAAAA) == 0)
{
return true;
}
return false;
}
public static void main(String[] args)
{
// Test Cases
System.out.println(isPowerOfFour(16));
System.out.println(isPowerOfFour(8));
System.out.println(isPowerOfFour(40));
System.out.println(isPowerOfFour(64));
// Note: 4 ^ 0 = 1
System.out.println(isPowerOfFour(1));
}
}
Output
true
false
false
true
true
// Include namespace system
using System;
public class Test
{
public static bool isPowerOfFour(int num)
{
if (num <= 0)
{
return false;
}
if ((num & (num - 1)) != 0)
{
return false;
}
if ((num & 0xAAAAAAAA) == 0)
{
return true;
}
return false;
}
public static void Main(string[] args)
{
Console.WriteLine(Test.isPowerOfFour(16));
Console.WriteLine(Test.isPowerOfFour(8));
Console.WriteLine(Test.isPowerOfFour(40));
Console.WriteLine(Test.isPowerOfFour(64));
Console.WriteLine(Test.isPowerOfFour(1));
}
}
Output
True
False
False
True
True
// Include header file
#include <iostream>
using namespace std;
class Test
{
public:
static bool isPowerOfFour(
int num)
{
if (num <= 0)
{
return false;
}
if ((num & (num - 1)) != 0)
{
return false;
}
if ((num & 0xAAAAAAAA) == 0)
{
return true;
}
return false;
}
};
int main(int argc, char **argv){
std::cout << Test::isPowerOfFour(16) << std::endl;
std::cout << Test::isPowerOfFour(8) << std::endl;
std::cout << Test::isPowerOfFour(40) << std::endl;
std::cout << Test::isPowerOfFour(64) << std::endl;
std::cout << Test::isPowerOfFour(1) << std::endl;
return 0;
};
Output
1
0
0
1
1
' Include namespace system
Imports System
public Class Test
Public Shared Function isPowerOfFour(num As Integer) As Boolean
if (num <= 0) Then
Return False
End If
if ((num And (num - 1)) <> 0) Then
Return False
End If
if ((num And 0xAAAAAAAA) = 0) Then
Return True
End If
Return False
End Function
Public Shared Sub Main(args As String())
Console.WriteLine(isPowerOfFour(16))
Console.WriteLine(isPowerOfFour(8))
Console.WriteLine(isPowerOfFour(40))
Console.WriteLine(isPowerOfFour(64))
Console.WriteLine(isPowerOfFour(1))
End Sub
End Class
Output
True
False
False
True
True
package main
import "os"
import "fmt"
func isPowerOfFour(num int)bool {
if (num <= 0) {
return false;
}
if ((num & (num - 1)) != 0) {
return false;
}
if ((num & 0xAAAAAAAA) == 0) {
return true;
}
return false;
}
func main(){
fmt.Println(isPowerOfFour(16));
fmt.Println(isPowerOfFour(8));
fmt.Println(isPowerOfFour(40));
fmt.Println(isPowerOfFour(64));
fmt.Println(isPowerOfFour(1));
}
Output
true
false
false
true
true
fn is_power_four(num: i32) -> bool
{
if num <= 0 {
return false;
}
if (num & (num - 1)) != 0 {
return false;
}
if (num & 0xAAAAAAAA) == 0 {
return true;
}
return false;
}
fn main()
{
println!("{}",is_power_four(16));
println!("{}", is_power_four(8));
println!("{}", is_power_four(40));
println!("{}", is_power_four(64));
println!("{}", is_power_four(1));
}
Output
true
false
false
true
true
class Test
def self.isPowerOfFour( num)
if (num <= 0)
return false
end
if ((num & (num - 1)) != 0)
return false
end
if ((num & 0xAAAAAAAA) == 0)
return true
end
return false
end
def self.main()
print(self.isPowerOfFour(16),"\n")
print(self.isPowerOfFour(8),"\n")
print(self.isPowerOfFour(40),"\n")
print(self.isPowerOfFour(64),"\n")
print(self.isPowerOfFour(1),"\n")
end
end
Test.main()
Output
true
false
false
true
true
object Main
{
def isPowerOfFour(num : Int) : Boolean=
{
if (num <= 0)
{
return false
}
if ((num & (num - 1)) != 0)
{
return false
}
if ((num & 0xAAAAAAAA) == 0)
{
return true
}
return false
}
def main(args : Array[String]) : Unit=
{
println(isPowerOfFour(16))
println(isPowerOfFour(8))
println(isPowerOfFour(40))
println(isPowerOfFour(64))
println(isPowerOfFour(1))
}
}
Output
true
false
false
true
true
import Foundation
func isPowerOfFour(_ num: Int) -> Bool
{
if (num <= 0)
{
return false;
}
if ((num & (num - 1)) != 0)
{
return false;
}
if ((num & 0xAAAAAAAA) == 0)
{
return true;
}
return false;
}
print(isPowerOfFour(16));
print(isPowerOfFour(8));
print(isPowerOfFour(40));
print(isPowerOfFour(64));
print(isPowerOfFour(1));
Output
true
false
false
true
true
fun isPowerOfFour(num: Int): Boolean
{
if (num <= 0)
{
return false;
}
if ((num and(num - 1)) != 0)
{
return false;
}
if ((num and - 1431655766) == 0)
{
return true;
}
return false;
}
fun main(args: Array < String > ): Unit
{
println(isPowerOfFour(16));
println(isPowerOfFour(8));
println(isPowerOfFour(40));
println(isPowerOfFour(64));
println(isPowerOfFour(1));
}
Output
true
false
false
true
true
function isPowerOfFour(num)
{
if (num <= 0)
{
return false;
}
if ((num & (num - 1)) != 0)
{
return false;
}
if ((num & 0xAAAAAAAA) == 0)
{
return true;
}
return false;
}
console.log(isPowerOfFour(16));
console.log(isPowerOfFour(8));
console.log(isPowerOfFour(40));
console.log(isPowerOfFour(64));
console.log(isPowerOfFour(1));
Output
true
false
false
true
true
Time Complexity
The time complexity of this algorithm is O(1), constant time. The reason is that the bitwise operations and comparisons are performed in constant time, regardless of the value of the input 'num'. There's no iteration or recursion involved that would lead to different time complexities for different inputs. Therefore, the algorithm's performance is not affected by the magnitude of 'num'.
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