Power of 系列

Power of 系列

如何判断一个数是否为基数 i 的 N 次方?

最简单的方式就是看它能不能不断地整除基数

// 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;
}

那有没有不需要递归或者循环直接判断的办法呢?

有,利用对数的性质,如果符合以下的换底公式

// e 可以为任意底数,b是题目要求的基数
logb(n) = loge(n) / loge(b)

那么 n 就一定可以通过 b 的 N 次方得到

因此问题就转化成 loge(n) / loge(b) 是整数的情况下返回 true ,否则返回 false

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

收获

  1. 换底公式的应用
  2. fmod(a, b) 函数返回 a / b 后余数的浮点形式
  3. fmod 第二个参数为 1,可以通过返回值是否为0判断第一个参数是否为整数

#math