检查一个整数是否是另一个整数的整数次幂

Question

这是一个面试题：“给定两个整数x和y，检查x是否为y的整数幂”（例如，对于x = 8和y = 2，答案是“true”，而对于x = 10和y = 2，“false”）。

The obvious solution is:

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

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

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

- Michael

---

实际上，我认为显而易见的解决方案是将x除以y，然后不断地将结果除以y，直到达到一个不能被y整除的数字。如果那个数字是1，那么x就是y的幂。 - JeremyP

很不幸，这里没有一个用户注意到每个发布的代码片段在x = ±1时都会失败。 - Nabb

不，我的适用于 x = +1（而且一个微不足道的 abs 可以解决负数问题）。然而 y == 0。 - The Archetypal Paul

Answer 1

你最好重复将 y 除以 x。第一次得到非零余数时，就知道 x 不是 y 的整数幂。

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

这个问题涉及到第一次迭代时奇偶点的处理。

- The Archetypal Paul

---

假设 x 是 123456789，y 是 2。请计算需要进行多少次乘以 y 的迭代才能得出答案，并计算需要进行多少次除法。 - JeremyP

它比乘法更好，因为它不会溢出。而且经过优化的代码可能会跳过您检测溢出的尝试。 - ruslik

是的，但平均情况要好得多。如果y不是x的因子（这在y次中有y-1次是真的），您将在第一次除法中发现它。 - The Archetypal Paul

@Paul - 在x86架构下，32位整数除法的速度大约比乘法慢10倍。你需要把这个因素考虑进分析中。 - Axn

@Axn：那么你可以把它乘以二，因为取模运算和除法一样耗时。 - Tony Delroy

Answer 2

它意味着 log_y(x) 应该是一个整数。不需要任何循环，在O(1)时间内完成。

public class PowerTest {

    public static boolean isPower(int x, int y) {
        double d = Math.log(Math.abs(x)) / Math.log(Math.abs(y));

        if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
            if (d == (int) d) {
                return true;
            } else {
                return false;
            }
        } else if (x > 0 && y < 0) {
            if ((int) d % 2 == 0) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

        System.out.println(isPower(-32, -2));
        System.out.println(isPower(2, 8));
        System.out.println(isPower(8, 12));
        System.out.println(isPower(9, 9));
        System.out.println(isPower(-16, 2));
        System.out.println(isPower(-8, -2));
        System.out.println(isPower(16, -2));
        System.out.println(isPower(8, -2));
    }

}

- user467871

---

在处理浮点数时，需要注意四舍五入问题。另外，“isPower(-8, -2)”这个函数的运行如何？ - JeremyP

是的，你说得对。我以为整数是正数。那么，我应该考虑它的绝对值版本。 - user467871

你应该尝试 isPower(1162261467, 3) x 大于1（问题中的整数） - user467871

+1 的确是一个不错的方法，但它并不是O(1)，而是O(log(x) + log(y))。此外，使用十进制更好，以避免舍入问题。 - Saeed Amiri

我认为你的代码在(17，-2)处失败了。（不过你可以进行修正）。 - azam

Answer 3

这个算法只需要 O(log N) 步骤来查找指数：

#define MAX_POWERS 100

int is_power(unsigned long x, unsigned long y) {
  int i;
  unsigned long powers[MAX_POWERS];
  unsigned long last;
  last = powers[0] = y;

  for (i = 1; last < x; i++) {
    last *= last; // note that last * last can overflow here!
    powers[i] = last;
  }
  while (x >= y) {
    unsigned long top = powers[--i];
    if (x >= top) {
      unsigned long x1 = x / top;
      if (x1 * top != x) return 0;
      x = x1;
    }
  }
  return (x == 1);
}

这段代码无法处理负数，但是可以通过一些条件代码很容易地解决，当 i = 1 时。

- salva

---

感谢您提出预先计算y的幂的想法！ - Michael

这个解决方案应该得到更多的赞。顺便说一下，如果 x > 1，powers[99] 绝对无法适合于一个无符号长整型。例如，如果 x == 2，那么 powers 99 大约是跟着一千万亿亿亿个零。 - jonderry

Answer 4

    double a=8;
    double b=64;

    double n = Math.log(b)/Math.log(a);
    double e = Math.ceil(n);

    if((n/e) == 1){
        System.out.println("true");
    } else{
       System.out.println("false");
    }

- Saddham Pathan

Answer 5

这看起来对于正数来说非常快，因为它找到所需幂的下限和上限，然后应用二分查找。

#include <iostream>
#include <cmath>
using namespace std;

//x is the dividend, y the divisor.
bool isIntegerPower(int x, int y)
{
    int low = 0, high;
    int exp = 1;
    int val = y;
    //Loop by changing exponent in the powers of 2 and
    //Find out low and high exponents between which the required exponent lies.
    while(1)
    {
        val = pow((double)y, exp);
        if(val == x)
            return true;
        else if(val > x)
            break;
        low = exp;
        exp = exp * 2;
        high = exp;
    }
    //Use binary search to find out the actual integer exponent if exists
    //Otherwise, return false as no integer power.
    int mid = (low + high)/2;
    while(low < high)
    {
        val = pow((double)y, mid);
        if(val > x)
        {
            high = mid-1;
        }
        else if(val == x)
        {
            return true;
        }
        else if(val < x)
        {
            low = mid+1;
        }
        mid = (low + high)/2;
    }
    return false;
}

int main()
{
    cout<<isIntegerPower(1024,2);
}

- bjskishore123

Answer 6

这里是一个Python版本，结合了@salva和@Axn的思路，并进行修改以不生成任何大于给定数字的数字，并且仅使用简单的存储（即无列表），通过反复削减感兴趣的数字来实现：

def perfect_base(b, n):
    """Returns True if integer n can be expressed as b**e where
    n is a positive integer, else False."""

    assert b > 1 and n >= b and int(n) == n and int(b) == b

    # parity check
    if not b % 2:
        if n % 2:
            return False  # b,n is even,odd
        if b == 2:
            return n & (n - 1) == 0
        if not b & (b - 1) and n & (n - 1):
            return False  # b == 2**m but n != 2**M
    elif not n % 2:
        return False  # b,n is odd,even

    while n >= b:
        d = b
        while d <= n:
            n, r = divmod(n, d)
            if r:
                return False
            d *= d
    return n == 1

- smichr

Answer 7

我会这样实现这个函数：

bool IsWholeNumberPower(int x, int y)
{
    double power = log(x)/log(y);
    return floor(power) == power;
}

由于我们正在检查整数，因此不需要像浮点比较一样在Delta内进行检查。

- Matt Ellen

---

现在的问题是“日志”是如何实现的，为什么它比循环更好。 - Michael

log(x)其中x是一个整数，不是一个整数。所以，你并没有处理整数。还要考虑IsWholeNumberPower(-8, -2)。答案应该是真的。 - JeremyP

在我看来，日志方法比循环更好，因为它清晰地表明了你的意图。只要你知道一个数字的对数除以另一个数字的对数会给你第二个数字被提高到第一位所需的幂，我想不出有什么更清晰的方法了（我假设大多数人在学校里学过这个，但我可能错了）。如果你正在寻找更快的代码，那么我无法告诉你，因为我没有在任何语言中测试过这个。 - Matt Ellen

@JeremyP：我的意思不是log（x）会给出一个整数，而是你只想检查 log（x）/log（y）是否是整数，因此检查答案是否在floor的delta范围内是不必要的。但是你是正确的，这对于负数不起作用。 - Matt Ellen

@Matt Ellen：是的，但由于log（x）是超越数，它将被四舍五入，同样地，log（y），log（x）/log（y）可能不会成为整数。 - JeremyP

Answer 8

经过再次考虑，不要这样做。对于负数 x 和/或 y，它不起作用。请注意，目前呈现的所有其他基于 log 的答案也都以完全相同的方式破坏。

以下是一个快速的通用解决方案（使用Java）：

static boolean isPow(int x, int y) {
    int logyx = (int)(Math.log(x) / Math.log(y));
    return pow(y, logyx) == x || pow(y, logyx + 1) == x;
}

pow() 是一个整数幂函数，例如在Java中的以下用法：

static int pow(int a, int b) {
    return (int)Math.pow(a, b);
}

这样做的原因是由于Math.pow提供了以下保证：“如果两个参数都是整数，则结果完全等于将第一个参数的幂次方提高到第二个参数的数学结果...”

使用对数而不是重复除法的原因是性能：虽然对数比除法慢，但差异很小。同时，它消除了循环的需要，从而为您提供了一个常数时间算法。

- NPE

Answer 9

在y等于2的情况下，有一种快速方法可以避免使用循环。这种方法可以扩展到y是某个更大的2的幂次的情况。

如果x是2的幂次，那么它的二进制表示中只有一个位被设置为1。有一种相当简单的位操作算法，可以在O(log n)的时间内计算一个整数的位数，其中n是整数的位数。许多处理器也有专门的指令可以将其作为单个操作处理，速度约为（例如）整数取反的速度。

然而，要扩展这种方法，首先需要采用稍微不同的方法来检查单个位。首先确定最低有效位的位置。同样，有一种简单的位操作算法，许多处理器也具有快速的专用指令。

如果这个位是唯一的位，则(1 << pos) == x。这里的优点在于，如果你正在测试4的幂次，那么你可以测试pos % 2 == 0（单个位在偶数位置）。对于任何2的幂次，你都可以测试pos % (y >> 1) == 0。

原则上，你可以对3的幂次和3的幂次的幂次进行类似的测试。问题在于你需要一个使用3进制的机器，这有点不太可能。你可以测试任何值x，以查看其在基数为y的表示中是否有单个非零数字，但这将会做更多的工作。以上利用了计算机以二进制方式工作的事实。

但在现实世界中可能不值得这样做。

- user180247

---

同样的思想可以应用于任何进制。虽然它不像移位操作那么简单，但只使用基本算术运算（ +， *， /）即可完成 。有关C语言中实现的详细信息，请参见我的回复。 - salva

有一种更快的检查2的幂次方的方法。(x & (x-1)) == 0 - Axn

@Axn - 我之前看过那个技巧，但我经常会忘记它。当然，它不比内置函数更快，但是它是可移植的。 - user180247

Answer 10

之前的回答都是正确的，我最喜欢Paul的回答。它简单而干净。 这里是他建议的Java实现：

public static boolean isPowerOfaNumber(int baseOrg, int powerOrg) {
    double base = baseOrg;
    double power = powerOrg;

    while (base % power == 0)
        base = base / power;
    // return true if base is equal 1
    return base == 1;
}

- grepit