检查一个整数是否是另一个整数的整数次幂 [英] Check if one integer is an integer power of another

问题描述

这是一个面试问题:给定2 个整数 x 和 y，检查 x 是否是 y 的整数幂"(例如，对于 x = 8 和 y = 2，答案是真"，对于 x = 10 和 y = 2假").

This is an interview question: "Given 2 integers x and y, check if x is an integer power of y" (e.g. for x = 8 and y = 2 the answer is "true", and for x = 10 and y = 2 "false").

显而易见的解决方案是:

The obvious solution is:

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

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

Now I am thinking about how to improve it.

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

Of course, I can check some special cases: e.g. both x and y should be either odd or even numbers, i.e. we can check the least significant bit of x and y. However I wonder if I can improve the core algorithm itself.

推荐答案

你最好反复将 y 分成 x.第一次得到非零余数时，您知道 x 不是 y 的整数幂.

You'd do better to repeatedly divide y into x. The first time you get a non-zero remainder you know x is not an integer power of y.

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

这在第一次迭代时处理您的奇数/偶数点.

This deals with your odd/even point on the first iteration.

这篇关于检查一个整数是否是另一个整数的整数次幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！