How to Check if Integer is Power of Four (C/C++) ?

Write a function to check whether a given 32-bit signed integer is a power of 4.

Example:
If num = 64, return true. and if num = 9, return false.

Straightforward Implementation to Determine Power of Four

The naive solution has complexity . The number can be divided by four until it is 1.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool isPowerOfFour(int num) {
        while (num >= 4) {
            if (num % 4 != 0) {
                return false;
            }
            num /= 4;
        }
        return num == 1;
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        while (num >= 4) {
            if (num % 4 != 0) {
                return false;
            }
            num /= 4;
        }
        return num == 1;
    }
};

Or, slightly shorter and concise:

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        while (num % 4 == 0) {
            num /= 4;
        }
        return num == 1;
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        while (num % 4 == 0) {
            num /= 4;
        }
        return num == 1;
    }
};

Alternatively, we can start from 1, multiple it by four until it exceeds the input:

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        int64_t x = 1;
        while (x < num) {
            x *= 4;
        }
        return x == num;
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        int64_t x = 1;
        while (x < num) {
            x *= 4;
        }
        return x == num;
    }
};

Check if Integer is Power of Four by Using Math Log function

We can compute the log base four of the input, if the resulting float number is itself an integer, then it is power of four. To compute the log base 4, we can use the log function and divided by log(4) that is log(b, N) = log(a, N)/log(a, b)

1
2
3
4
5
6
7
8

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        double x = log(num)/log(4);
        return (int)x == x;
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        double x = log(num)/log(4);
        return (int)x == x;
    }
};

Recursive Check of Power of Four

Using the same idea, but recursively, one can write a code like this:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num < 1) {
            return false;
        }
        if (num == 1) {
            return true;
        }
        return ((num % 4 == 0) && (isPowerOfFour(num / 4)));
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num < 1) {
            return false;
        }
        if (num == 1) {
            return true;
        }
        return ((num % 4 == 0) && (isPowerOfFour(num / 4)));
    }
};

Modern compilers are able to optimise this tail-recursion into iterative loops.

Using Bit Tweaks to Check Integer Power of Four

We know that if number is power of two, it satisfies that n & (n – 1) equals zero, that is: n & (n – 1) removes the least significant bit, leaving the number (that is power of two) zero.

We also know that mathematically, can be divided by 3, so we have:

1
2
3
4
5
6
7

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) 
                && ((num - 1) % 3 == 0);
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) 
                && ((num - 1) % 3 == 0);
    }
};

Also, if we interpret the number in binary form, we can see that the only set 1 for the number (power of four) has to be in the odd position. So, if we perform the bit-and for this number and 0x55555555, the result will be positive.

1
2
3
4
5
6
7

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) 
                && ((num & 0x55555555));
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) 
                && ((num & 0x55555555));
    }
};

Both the last two approach have running time complexity O(1).

–EOF (The Ultimate Computing & Technology Blog) —