Posted on by Kalkicode
Code Mathematics

# 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 $16 = 4^2$.
• 8 is not a power of 4 because it cannot be expressed in the form $4^x$.
• 40 is not a power of 4 for the same reason.
• 64 is a power of 4 because $64 = 4^3$.
• 1 is a power of 4 because $4^0 = 1$.

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

1. If the given number num is less than or equal to 0, it cannot be a power of 4, so return false.
2. 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 return false.
3. 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 return true.

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

1. If 'num' is non-positive, return false since no negative number or zero can be a power of 4.
2. 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.
3. 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'.

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