Check for Power of 4

Given an integer n, find whether it is a power of 4 or not.

Example :

Input : n = 16
Output : true
Explanation: 16 is a power of 4

Input : 20
Output : false
Explanation: 20 is not a power of 4

Using Bit Manipulation - O(log n) Time and O(1) Space

The idea is to first check whether the number is a power of 2 (i.e., it has only one set bit), and then ensure that the position of this set bit is at an even index (counting from 0), which guarantees it is a power of 4. This can be verified using bit operations by confirming that n & (n - 1) == 0 and the set bit lies at an even position.

#include <iostream>
using namespace std;

bool isPowerOfFour(int n) {
    int count = 0;

    // Check if n is power of 2 (only one set bit)
    if (n > 0 && (n & (n - 1)) == 0) {

        // Count number of shifts (position of set bit)
        while (n > 1) {
            n >>= 1;
            count++;
        }

        // Check if position is even
        return (count % 2 == 0);
    }

    return false;
}

int main() {
    int n = 64;

    if (isPowerOfFour(n))
        cout << "true";
    else
        cout << "false";

    return 0;
}

import java.io.*;
class GFG {

    static boolean isPowerOfFour(int n) {
        int count = 0;

        // Check if n is power of 2
        if (n > 0 && (n & (n - 1)) == 0) {
            
            // Count number of shifts (position of set bit) 
            while (n > 1) {
                n >>= 1;
                count++;
            }

            return (count % 2 == 0);
        }

        return false;
    }

    public static void main(String[] args) {
        int n = 64;

        if (isPowerOfFour(n))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

def isPowerOfFour(n):
    count = 0

    # Check if n is power of 2
    if n > 0 and (n & (n - 1)) == 0:
        
        # Count number of shifts (position of set bit) 
        while n > 1:
            n >>= 1
            count += 1

        return count % 2 == 0

    return False


if __name__ == "__main__":
    n = 64

    if isPowerOfFour(n):
        print("true")
    else:
        print("false")

using System;

class GFG {

    static bool isPowerOfFour(int n) {
        int count = 0;

        // Check if n is power of 2
        if (n > 0 && (n & (n - 1)) == 0) {
             
            // Count number of shifts (position of set bit)  
            while (n > 1) {
                n >>= 1;
                count++;
            }

            return (count % 2 == 0);
        }

        return false;
    }

    static void Main() {
        int n = 64;

        if (isPowerOfFour(n))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

function isPowerOfFour(n) {
    let count = 0;

    // Check if n is power of 2
    if (n > 0 && (n & (n - 1)) === 0) {

        // Count number of shifts (position of set bit)
        while (n > 1) {
            n = n >> 1;
            count++;
        }

        return count % 2 === 0;
    }

    return false;
}

// Driver Code
let n = 64;

if (isPowerOfFour(n))
    console.log("true");
else
    console.log("false");

True

Explanation: The binary representation of 64 is 1000000, which has only one set bit, so it is a power of 2. The position of this set bit (counting from 0) is 6, which is an even index. Since both conditions are satisfied, the number 64 is a power of 4.

Logarithmic Approach - O(1) Time and O(1) Space

If a number n is a power of 4, then log₄(n) will always be an integer. So, we compute log₄(n) and check whether its floor value is equal to its ceil value; if both are equal, it means the value is an integer and hence n is a power of 4.

#include <iostream>
#include <cmath>
using namespace std;

double logn(int n, int base) {
    return log(n) / log(base);
}

bool isPowerOfFour(int n) {
    if (n <= 0) return false;

    double val = logn(n, 4);
    return floor(val) == ceil(val);
}

int main() {
    int n = 64;

    if (isPowerOfFour(n))
        cout << "true";
    else
        cout << "false";

    return 0;
}

class GFG {

    static double logn(int n, int base) {
        return Math.log(n) / Math.log(base);
    }

    static boolean isPowerOfFour(int n) {
        if (n <= 0) return false;

        double val = logn(n, 4);
        return Math.floor(val) == Math.ceil(val);
    }

    public static void main(String[] args) {
        int n = 64;

        if (isPowerOfFour(n))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

import math

def logn(n, base):
    return math.log(n) / math.log(base)

def isPowerOfFour(n):
    if n <= 0:
        return False

    val = logn(n, 4)
    return math.floor(val) == math.ceil(val)


if __name__ == "__main__":
    n = 64

    if isPowerOfFour(n):
        print("true")
    else:
        print("false")

using System;

class GFG {

    static double logn(int n, int baseVal) {
        return Math.Log(n) / Math.Log(baseVal);
    }

    static bool isPowerOfFour(int n) {
        if (n <= 0) return false;

        double val = logn(n, 4);
        return Math.Floor(val) == Math.Ceiling(val);
    }

    static void Main() {
        int n = 64;

        if (isPowerOfFour(n))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

function logn(n, base) {
    return Math.log(n) / Math.log(base);
}

function isPowerOfFour(n) {
    if (n <= 0) return false;

    let val = logn(n, 4);
    return Math.floor(val) === Math.ceil(val);
}

// Driver Code
let n = 64;

if (isPowerOfFour(n))
    console.log("true");
else
    console.log("false");

True

Explanation: For n = 64, we compute log base 4 of 64, which gives 3. Since this value is an integer, its floor and ceil values are equal. Hence, 64 is a power of 4.

Bit Masking Technique - O(1) Time and O(1) Space

The idea is to first check whether the number has only one set bit (i.e., it is a power of 2 using n & (n - 1) == 0). Then, we ensure that this set bit is not in any odd position by verifying that n & 0xAAAAAAAA == 0, since this mask has all bits set at odd positions. If both conditions are satisfied, the number is a power of 4.

#include <iostream>
using namespace std;

bool isPowerOfFour(int n) {
    return (n > 0) && ((n & (n - 1)) == 0) && ((n & 0xAAAAAAAA) == 0);
}

int main() {
    int n = 64;

    if (isPowerOfFour(n))
        cout << "true";
    else
        cout << "false";

    return 0;
}

class GFG {

    static boolean isPowerOfFour(int n) {
        return (n > 0) && ((n & (n - 1)) == 0) && ((n & 0xAAAAAAAA) == 0);
    }

    public static void main(String[] args) {
        int n = 64;

        if (isPowerOfFour(n))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

def isPowerOfFour(n):
    return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0


if __name__ == "__main__":
    n = 64

    if isPowerOfFour(n):
        print("true")
    else:
        print("false")

using System;

class GFG {

    static bool isPowerOfFour(int n) {
        return (n > 0) && ((n & (n - 1)) == 0) && ((n & 0xAAAAAAAA) == 0);
    }

    static void Main() {
        int n = 64;

        if (isPowerOfFour(n))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

function isPowerOfFour(n) {
    return n > 0 && (n & (n - 1)) === 0 && (n & 0xAAAAAAAA) === 0;
}

// Driver Code
let n = 64;

if (isPowerOfFour(n))
    console.log("true");
else
    console.log("false");

True

Note: A number can be identified as a power of 4 if it has only one set bit (i.e., it is a power of 2) and the number of trailing zeros is even. Using built-in functions like "__builtin_ctz(n)" in C++ or "Integer.numberOfTrailingZeros(n)" in Java, this condition can be checked efficiently in a single line.

Perfect Square + Modulo Approach - O(1) Time and O(1) Space

A number is a power of 4 if it is first a power of 2 (only one set bit), and additionally satisfies n % 3 == 1, since all powers of 4 leave a remainder of 1 when divided by 3.

#include <iostream>
using namespace std;

bool isPowerOfFour(int n) {
    return (n > 0) && ((n & (n - 1)) == 0) && (n % 3 == 1);
}

int main() {
    int n = 64;

    if (isPowerOfFour(n))
        cout << "true";
    else
        cout << "false";

    return 0;
}

class GFG {

    static boolean isPowerOfFour(int n) {
        return (n > 0) && ((n & (n - 1)) == 0) && (n % 3 == 1);
    }

    public static void main(String[] args) {
        int n = 64;

        if (isPowerOfFour(n))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

def isPowerOfFour(n):
    return n > 0 and (n & (n - 1)) == 0 and (n % 3 == 1)

if __name__ == "__main__":
    n = 64

    if isPowerOfFour(n):
        print("true")
    else:
        print("false")

using System;

class GFG {

    static bool isPowerOfFour(int n) {
        return (n > 0) && ((n & (n - 1)) == 0) && (n % 3 == 1);
    }

    static void Main() {
        int n = 64;

        if (isPowerOfFour(n))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

function isPowerOfFour(n) {
    return n > 0 && (n & (n - 1)) === 0 && (n % 3 === 1);
}

// Driver Code
let n = 64;

if (isPowerOfFour(n))
    console.log("true");
else
    console.log("false");

True

Explanation: First, we check whether 64 is a power of 2. The binary representation of 64 is 1000000, which has only one set bit, so it satisfies this condition. Next, we check the modulo condition: 64 % 3 = 1. Since both conditions are satisfied so 64 is a power of 4.