各种Power of N的算法总结

最近刷题刷到了好多Power of N，也就是判断一个数是否是N的各种次方。下面总结下大概的算法。

1. N为2

这种情况是比较特殊的，因为假如N是2的各种次方结果，那么将它转为二进制，必定是最高位是1，其它位为0，这种情况很好办，只要把最高位的0给抹去。将最高位的0抹去的算法之前也发过了，只需要

n & (n - 1)

就可以消去了，消去之后看结果是否为0,0的话那么就成立。

1. N非2

这种情况下，最原始的方法就是循环不断的除以N，假设最后的结果为1则成立。

另外一种做法是，根据对数换底的公式来做。假设M是N的次方数，则lognM必定为整数，在这里为了记录方便，小写的为底数。然而我们没法直接计算该表达式，库函数内置了log10函数来计算以10为底的表达式的结果，于是我们根据换底公式

lognM = logoM / logoN

于是表达式变为了

lognM = log10M / log10N

我们只需要判断该结果是否为整数就行了，以下为代码实现

// logca = logdc/logda
if (num <= 0) {
    return false;
}
auto ret = log10(num) / log10(4);
int nret = int(ret);
return ((long double)(nret) - ret) == 0;

1. 取巧算法

还有各种的取巧算法，见过在限定的条件下，比如输入M是int32位有符号数，假如计算M是否是3的次方数，则我们先把在2^31-1内最大的3的次方数先算出来，然后除以N，假设整除，则成立。