Powers of N: Two Ways to Check

How do you tell if a number is a power of base i?

The simple way is to keep dividing by the base until it won’t go evenly anymore.

// i = 2
bool isPowerOfTwo(int n) {
    while(n!=0 && (n & 1) == 0) n>>=1;
    return n == 1 ? true : false;
}


// i = 3
bool isPowerOfThree(int n) {
    while(n>1 && n%3==0) n/=3;
    return n == 1 ? true : false;
}

But can we do this without loops or recursion?

Yes. We use logarithm properties. If this change of base formula holds:

// e can be any base, b is the required base
logb(n) = loge(n) / loge(b)

Then n must be some power of b.

So the problem becomes: return true when loge(n) / loge(b) is an integer, otherwise false.

bool isPowerOfFour(int n) {
    return fmod(log10(n)/log10(4), 1)==0;
}

What I learned

1. Change of base formula application
2. fmod(a, b) returns the floating-point remainder after division
3. When the second parameter of fmod is 1, you can check if the first parameter is an integer by seeing if the return value is 0

#math