algorithm - 检查一个整数是否是另一个整数的幂

Question

这是一个 interview question :“给定 2 个整数 x 和 y，检查 x 是否是 y 的整数次方”(例如，对于 x = 8 和 y = 2，答案是“真”，对于 x = 10 和 y = 2，答案是“假”)。

显而易见的解决方案是:

int n = y; while(n < x) n *= y; return n == x

现在我正在考虑如何改进它。

当然，我可以检查一些特殊情况:例如两者 x和 y应该是奇数或偶数，即我们可以检查 x 的最低有效位和 y .但是我想知道我是否可以改进核心算法本身。

Answer 1

您最好将 y 重复划分为 x。第一次得到非零余数时，您知道 x 不是 y 的整数次幂。

while (x%y == 0)  x = x / y
return x == 1

这会处理第一次迭代中的奇数/偶数点。