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

New Comment





Categories
Relative Post