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

问题描述

这是一个<一个href="http://www.glassdoor.com/Interview/Given-2-numbers-x-and-y-check-if-x-is-an-integer-power-of-y-For-instance-x-8-y-2-would-return-true-and-x-10-and-y-QTN_111532.htm">interview问题：在考虑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 和是应该是奇数还是偶数，也就是说，我们可以检查的最低显著位 X 和是。不过，我不知道我是否能够提高核心算法本身。

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屋！